CCC '18 S3 - RoboThieves

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2018 Stage 1, Senior #3

A robot has stolen treasure from a factory and needs to escape without getting caught. The factory can be modelled by an N by M grid, where the robot can move up, down, left, or right.

Each cell of the grid is either empty, a wall, a camera, a conveyor, or the robot's initial position. The robot can only walk on empty cells (denoted by .) or conveyors. The first row, last row, first column and last column of the grid consists of walls (denoted by W), and there may be walls in other cells.

Conveyors cause the robot to move in a specific direction, denoted by L, R, U, D for left, right, up, down respectively. The robot is unable to move on its own while on a conveyor. It is possible that the robot can become stuck forever on conveyors.

Cameras (denoted by C) can see in all four directions up, down, left, and right, but cannot see through walls. The robot will be caught if it is in the same cell as a camera or is seen by a camera while not on a conveyor. Conveyors are slightly elevated, so the robot cannot be caught while on a conveyor, but cameras can see empty cells on the other side of conveyors.

The robot is initially at the cell denoted by S. The exit could be at any of the empty cells. For each empty cell, determine the minimum number of steps needed for the robot to move there without being caught, or determine that it is impossible to move there. A step consists of moving once up, down, left or right. Being moved by a conveyor does not count as a step.

Input Specification

The first line of input contains two integers N and M (4 \le N, M \le 100). The next N lines of input will each contain M characters, each of which is one of the eight characters W, ., C, S, L, R, U, or D.

There will be exactly one S character and at least one . character. The first and last character of every row and column will be W.

For 5 of the 15 marks available, there are no cameras or conveyors.

For an additional 5 of the 15 marks available, there are no conveyors.

Output Specification

For each empty cell, print one line with one integer, the minimum number of steps for the robot to move to this empty cell without being caught or -1 if it is impossible to move to this empty cell.

The output should be in row major order; the order of empty cells seen if the input is scanned line by line top-to-bottom and then left-to-right on each line. See the sample outputs for examples of row major order output.

Sample Input 1

4 5
WWWWW
W.W.W
WWS.W
WWWWW

Sample Output 1

-1
2
1

Explanation for Sample Output 1

The robot cannot move to the top left empty cell because it is blocked by walls.

The top right empty cell can be reached in 2 steps and the bottom right empty cell can be reached in 1 step.

Sample Input 2

5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW

Sample Output 2

2
1
3
-1
-1
1

Explanation for Sample Output 2

The empty cell to the immediate left of the robot is seen by the camera so the robot cannot move there.

The empty cell right below the R conveyor is also seen by the camera as conveyors do not block the sight of cameras.

Note that the robot can use the U and L conveyors to avoid getting caught by the camera.

If the robot moves to the R conveyor, it will become stuck there forever.


Comments


  • 3
    devnarula  commented on June 16, 2020, 3:36 p.m.

    can someone assist, I am getting WA on case #2 of the last bacth


    • 0
      noYou  commented on June 16, 2020, 5:21 p.m.

      Did you check for the case where you spawn right beside the camera?


      • 1
        devnarula  commented on June 18, 2020, 12:26 p.m.

        thanks for your help. that was the only case i was missing


  • 2
    aaronhe07  commented on June 5, 2020, 2:09 p.m.

    Wow that took me about ten tries


    • 1
      Ibby  commented on June 8, 2020, 1:45 p.m.

      Same


  • 0
    bigboy2  commented on May 24, 2020, 6:56 p.m.

    Can someone take a look at my code I'm getting WA on case #1 of the last batch


  • 8
    device  commented on Oct. 16, 2019, 2:57 p.m. edited

    tzak_el cheesed this problem.


  • 8
    Unturned3  commented on Feb. 2, 2019, 4:00 a.m.

    Hello, I'm getting WA for Batch 5 Case 2, and I couldn't find any bugs with my program. Are there any special cases/pitfalls that I'm unaware of? I already included code to handle the situation where the robot spawns in the sight of a camera, and I couldn't think of any other corner cases.

    Thanks for helping!


    • 10
      NewAccount  commented on Aug. 6, 2019, 3:36 p.m. edit 4

      Consider The Case:

      4 6  
      WWWWWW
      W.LLSW
      W....W
      WWWWWW

      Output Should Be:

      1
      2
      3
      2
      1

      • 1
        TingHoMarcus  commented on Oct. 28, 2019, 8:38 a.m.

        Mine can past your testcase with no problem, but I am still failing that testcase


        • 1
          asdfg9240  commented on Jan. 17, 2020, 4:21 a.m.

          i also could solve NewAccount's test case but still got batch #5 case #2 wrong. make sure you can solve:

          4 4
          WWWW
          WSDW
          W..W
          WWWW
          
          
          4 4
          WWWW
          WS.W
          WR.W
          WWWW
          
          4 4
          WWWW
          WDSW
          W..W
          WWWW
          
          4 4
          WWWW
          W.SW
          W.LW
          WWWW

          etc.. both dots should be 1, one of them should not be 2.


        • 6
          Aaeria  commented on Oct. 29, 2019, 12:29 p.m.

          The test cases for this problem can be found at https://www.cemc.uwaterloo.ca/contests/computing/2019/index.html


  • 5
    gandhiisback  commented on Jan. 23, 2019, 1:36 p.m.

    I don't think the DMOJ judge is reflective of the CCC Grader. My python code works fine on CCC Grader but TLEs on DMOJ.

    https://dmoj.ca/submission/1214670

    https://gyazo.com/2035b158e7266b140435bc1d188128a7


    • 5
      Riolku  commented on Jan. 23, 2019, 7:22 p.m.

      Although this is the case, if your approach is correct, you can certainly solve this problem on DMOJ.


    • 15
      wleung_bvg  commented on Jan. 23, 2019, 4:35 p.m.

      Try submitting with PyPy


      • 11
        Kirito  commented on Jan. 23, 2019, 11:07 p.m.

        The CCC grader uses PYPY instead of CPython.


  • 4
    p1geon  commented on Jan. 14, 2019, 12:34 a.m.

    Can a conveyor lead to a wall?


    • 6
      JustinXu  commented on Jan. 14, 2019, 7:57 a.m.

      Indeed.


  • 1
    Aarya  commented on Oct. 21, 2018, 10:16 p.m.

    Any way to make java code faster? TLE on a couple cases with large inputs.


  • 0
    MowMowChow  commented on Oct. 12, 2018, 6:14 p.m.

    Ideas on why I'm getting an 'Invalid Return'? (any help would be much appreciated :D )


  • 0
    Cameron  commented on July 6, 2018, 1:51 p.m.

    When I upload the program, there is a tle, and rte, and sometimes, no output. I don't understand, because it seems to work when I test the program on my ide. What's going on?


  • 16
    GeoHD  commented on Feb. 27, 2018, 8:24 p.m. edited

    There is one scenario where the robot spawns right next to a camera.


    • 8
      Plasmatic  commented on Oct. 2, 2018, 2:41 p.m. edited

      I heard that tripped quite a few people on the CCC


  • 0
    william9518  commented on Feb. 18, 2018, 9:03 p.m.

    I'm getting 10/15 due to Batch #3 saying "clipped". What does this mean? What is the correct answer for the first test case of Batch #3? https://gyazo.com/6224aad6d59e8f8a5fe6e520db78f6f2


    • 5
      aeternalis1  commented on Feb. 18, 2018, 10:56 p.m.

      When you fail a test case and your program has output (with partial output enabled), you are allowed to see a limited amount of your output. As for what you are getting wrong, I suggest you think about possible edge cases. If you ever need in-depth help, visit the dmoj slack channel at https://slack.dmoj.ca/.


  • 0
    Darcy_Liu  commented on Feb. 18, 2018, 4:22 p.m.

    Can't get partial on this one


    • 55
      CopyPastePolice  commented on Oct. 13, 2018, 4:29 p.m. edited

      Darcy_Liu, YOU'RE UNDER ARREST

      It has come to our attention that you've been copying and pasting solutions on DMOJ. This does not show good sportsmanship and is unfair to DMOJistan. Blindly copying and pasting code does not improve your own abilities and breaks DMOJ's rules.

      Proof:

      Example 1: COCI '14 Contest 7 #3 ACM - https://dmoj.ca/problem/coci14c7p3

      Offender's Code: https://dmoj.ca/submission/1046085

      Source: https://dmoj.ca/src/1036320

      Example 2: CCC '10 S3 - Firehose - https://dmoj.ca/problem/ccc10s3

      Offender's Code: https://dmoj.ca/src/1026958

      Source: https://dmoj.ca/src/375814


      • 34
        Darcy___Liu  commented on June 12, 2019, 6:52 p.m. edit 2

        Darcy_Liu is the enemy of the people. He tries to copy code but the state is always watching.


        • 8
          DiscoverMeme  commented on April 8, 2020, 1:29 p.m.

          Darcy___Liu has betrayed the revolution.

          Edit 1:

          Do not believe their lies. Darcy_Liu did not copy code.

          Edit 2:

          Darcy_Liu is the enemy of the people. He tries to copy code but the state is always watching.


          • 2
            Darcy___Liu  commented on April 9, 2020, 8:48 p.m.

            It appears that you have yet to update your history books and databases. CopyPastePolice is an ally to the state and we are preparing an invasion of PETHCS.


      • -15
        dagsi  commented on Oct. 15, 2018, 9:55 a.m.

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 17
          Plasmatic  commented on Oct. 15, 2018, 10:19 a.m.

          you have to have solved the problems first to view the source links


          • 6
            harry7557558  commented on April 5, 2020, 11:17 p.m.

            How does CopyPastePolice view other people's submissions with only 1 problem solved?


            • 34
              AQT  commented on April 6, 2020, 12:38 a.m.

              cuz ur mom lol


              • 4
                thomas_li  commented on April 6, 2020, 12:48 p.m.

                gottem


      • -4
        Plasmatic  commented on Oct. 13, 2018, 7:34 p.m. edited

        When daxi gets exposed

        Also the ACM submission was made during class lol