CCC '18 S3 - RoboThieves - Olympiads Online Judge

CCC '18 S3 - RoboThieves

Points: 12 (partial)

Time limit: 0.5s

Memory limit: 256M

Author:

Problem types

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$ ~N~ by $M$ ~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$ ~N~ and $M$ ~M~ $(4 \le N, M \le 100)$ ~(4 \le N, M \le 100)~. The next $N$ ~N~ lines of input will each contain $M$ ~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$ ~5~ of the $15$ ~15~ marks available, there are no cameras or conveyors.

For an additional $5$ ~5~ of the $15$ ~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$ ~2~ steps and the bottom right empty cell can be reached in $1$ ~1~ step.

Sample Input 2

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

Sample Output 2

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

0

wwwddddz commented on Dec. 11, 2023, 1:10 p.m. ← edit 2 →

do any body know why I passed batch 1245 but can not pass batch 3 case 1?

3
aldenstripes commented on Feb. 4, 2024, 9:23 p.m.
Probably because the test case starts with a camera already seeing the starting point.

Try this test case:

4 4 WWWW WS.W WCWW WWWW

You should get:

-1

3

jerrycui07 commented on Oct. 18, 2023, 1:21 a.m.

Is it possible a conveyor will just push the robot into a wall? Like say there's a test case with a line "WL". If the robot steps on the L, what happens to it?

2

MrBloc01 commented on Dec. 5, 2023, 4:54 a.m.

Look at sample case 2, the robot will be stuck forever in this case.

15
pCode14 commented on Feb. 9, 2022, 2:02 p.m. ← edited →
Not sure anyone really needs this, but due to the amount of help I needed and to help with others who will come across this problem, I've compiled some ideas in case you need the help.

Issues I had when implementing:

Replacing camera squares: I initially thought that it was a great idea to replace empty spaces covered by cameras with other characters - however this proved to be troublesome. It is possible to make this method work, however personally, I think the more efficient method would be to store invalid squares separately. Here's the reason why - the rest is left as exercise to the reader: a camera covered square does not guarantee an open square

BFS implementation: If you are using BFS (which you probably should be) make sure that what you are checking is accurate. This includes checking both what square you are on and what square you are moving to. Hint (not given as full to stay an exercise to the reader): if you are using a visited array and cross an infinite loop of conveyors, how do you ensure you only go around a maximum of one time through the use of your visited?

Filling your array with a preliminary large int: This is only a note for C++ users and is in fact very minor. Using "memset" does not fill an array; instead use the "std::fill" function.

Two conveyor case: Once you have fixed up the conveyor loop, this likely isn't much of an issue but is still worthwhile to check: two consecutive conveyors is a bit of a corner case that may not work

Hopefully this leaves a lot of the problem as an exercise, but still helps in the case that you are severely stuck in finding corner cases - not all your issues might be considered here as I use C++, but maybe it can help out. I highly recommend also checking out other cases in the comments to help fix your work.

0

vishnus commented on June 2, 2022, 1:35 a.m.

orz pavi

3

jo3_l commented on Sept. 25, 2021, 9:41 p.m. ← edited →

My solution is WAing on the 2nd test case of batch 5, but I'm not sure what's wrong. I have checked all related comments and am handling all edge cases I know of.

I've also tested my solution locally using the official test data and there was no difference between my output and the expected output (checked via diff), which leads me to suspect that my code is relying upon undefined behavior somewhere. Unfortunately, I'm not skilled enough to find it.

If someone could help, that'd be great. Thanks!

8

lilweege commented on Sept. 26, 2021, 7:15 a.m.

The judge server compiles your program with -O2, which in your case seems to cause problems with g++; specifically on line 132 and 133 (storing your index in a variable rather than inline seems to fix it). Regardless though, submitting your original solution with clang++ seems to pass just fine.

3

jo3_l commented on Sept. 26, 2021, 6:27 p.m. ← edit 3 →

Ugh. Thank you so much, really appreciate it. In hindsight, I'm actually somewhat surprised that it doesn't WA earlier / at all on Clang.

10
WSM_simon commented on Aug. 23, 2021, 10:38 p.m.
Anyone cannot pass batch 5 Considering this case

6 6 WWWWWW WRRRDW WU.WDW WUWSDW WULLLW WWWWWW

the answer should be

-1

7

zhenga1 commented on Feb. 10, 2021, 1:38 p.m. ← edit 4 →

Also, guys, there is a very annoying test case where the conveyor forms a loop and the robot is stuck on conveyors forever. It is batch 3 test 2. I got maximum recursion depth exceeded.

1

stevenning203 commented on Jan. 9, 2021, 1:29 a.m. ← edit 5 →

How do I check the distances when using a BFS using a queue? I am currently storing the distances inside structs but I have to reset the whole matrix every time I BFS and I think it's causing TLE. Also, I don't know how to make it so that the robot prioritizes taking the path with a bunch of conveyors because my program treats conveyors as normal points but it doesn't add one to the distance so sometimes it thinks that the shortest path is the path with a bunch of dots instead of a path with a conveyor.

EDIT: I used while loops to fix the shortest path conveyor issue but I still don't know how to store distances the optimal way. Could someone guide me? Thanks.

3

DynamicSquid commented on Jan. 9, 2021, 3:31 a.m. ← edit 3 →

For the distances, you can store a dist variable inside your struct, and every time you move to a cell, set that cell's distance to the current distance travelled.

Also for conveyors, you can think of them as moving twice in the same step. And since this is a BFS, you are guaranteed to find the shortest path

0

stevenning203 commented on Jan. 9, 2021, 4:14 a.m. ← edited →

Yea that's what I did, I thought it would TLE but I only have 1 TLE and that's on batch 1 so I think storing the dist inside the structs was actually fine. I'm still not sure what to do about that 1 TLE though. Thanks for the response.

Edit: Nevermind I finally managed to solve it by memoizing any dots passed by on any BFS so that if you BFS them again there is no need to call the function and instead you can just use an array lookup.

4

DynamicSquid commented on Dec. 28, 2020, 11:52 p.m.

I'm getting WA on Batch #3 Case #2 and Batch #5 Case #2. I read all the comments and made sure my code works for all special cases like when you start next to a camera, or a never ending conveyor. Is there something else I'm missing?

7
BalintR commented on Dec. 29, 2020, 4:13 a.m.
Consider the following test case:

5 5 WWWWW W..SW WC..W W.C.W WWWWW

The output should be all -1s.

5

DynamicSquid commented on Dec. 29, 2020, 5:53 p.m. ← edited →

Oh I see what I did wrong! I iterated through each camera, and then directly turned the invalid positions into walls.

I should of stored the invalid positions in a separate array instead of modifying the grid directly.

Thanks!

7

jasone commented on July 30, 2020, 2:56 a.m. ← edited →

For anyone stuck on Batch 5 Case 2, make sure you have some code dealing with if the robot finds himself stuck on two conveyors and cannot escape (WLRW). (Besides also having some code to check if you spawn next to a camera) That was the issue for me.

6

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

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

4

noYou commented on June 16, 2020, 9:21 p.m.

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

2

devnarula commented on June 18, 2020, 4:26 p.m.

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

8

Unturned3 commented on Feb. 2, 2019, 9: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!

25
NewAccount commented on Aug. 6, 2019, 7: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, 12:38 p.m.

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

9
asdfg9240 commented on Jan. 17, 2020, 9: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.

7

Aaeria commented on Oct. 29, 2019, 4:29 p.m.

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

6

gandhiisback commented on Jan. 23, 2019, 6: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. 24, 2019, 12:22 a.m.

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

17

wleung_bvg commented on Jan. 23, 2019, 9:35 p.m.

Try submitting with PyPy

15

Kirito commented on Jan. 24, 2019, 4:07 a.m.

The CCC grader uses PYPY instead of CPython.

3

p1geon commented on Jan. 14, 2019, 5:34 a.m.

Can a conveyor lead to a wall?

5

JustinXu commented on Jan. 14, 2019, 12:57 p.m.

Indeed.

1

Aarya commented on Oct. 22, 2018, 2:16 a.m.

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

3

loltrollkill commented on Oct. 22, 2018, 7:47 p.m.

look here under java

20

GeoHD commented on Feb. 28, 2018, 1:24 a.m. ← edited →

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

8

Plasmatic commented on Oct. 2, 2018, 6:41 p.m. ← edited →

I heard that tripped quite a few people on the CCC

0

william9518 commented on Feb. 19, 2018, 2:03 a.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

7

aeternalis1 commented on Feb. 19, 2018, 3:56 a.m. ← edited →

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 discord channel at https://discord.com/invite/EgJVpxz.

-1

Darcy_Liu commented on Feb. 18, 2018, 9:22 p.m.

Can't get partial on this one

62

CopyPastePolice commented on Oct. 13, 2018, 8: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

35

Darcy___Liu commented on June 12, 2019, 10:52 p.m. ← edit 2 →

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

9

DiscoverMeme commented on April 8, 2020, 5: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.

3

Darcy___Liu commented on April 10, 2020, 12:48 a.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.

-19

dagsi commented on Oct. 15, 2018, 1:55 p.m.

None of those links work.

This comment is hidden due to too much negative feedback. Show it anyway.

21

Plasmatic commented on Oct. 15, 2018, 2:19 p.m.

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

14

harry7557558 commented on April 6, 2020, 3:17 a.m.

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

58

AQT commented on April 6, 2020, 4:38 a.m.

cuz ur mom lol

13

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

gottem

-4

Plasmatic commented on Oct. 13, 2018, 11:34 p.m. ← edited →

When daxi gets exposed

Also the ACM submission was made during class lol