DMOPC '13 Contest 1 P4 - AFK
View as PDFKids are spending far too much time on their computers nowadays. Once in a while, they have to go to the washroom. Given a floor map of a kid's home, output the minimum number of steps it will take the kid to get to the washroom. If the washroom cannot be reached in fewer than 60 steps (a step is one move in a north, south, east, or west direction), then output #notworth.
Your input will start with an integer (
), where
is the number of test cases, and then followed by
and
(
) where
and
are the length and width, respectively, of each floor map. The next
lines will contain
characters, each one of the following:
Ois open space (you can pass through these)Xis wall (you can't pass through these)Cis computer (this is where you start)Wis washroom (this is where you want to go)
Sample Input
2
27 5
OOCOOOOOOOOOOOOOOOOOOOOOOOO
XXXXXXXXXXXXXXXXXXXXXXXXXXO
OOOOOOOOOOOOOOOOOOOOOOOOOOO
OXXXXXXXXXXXXXXXXXXXXXXXXXX
OOOOOOOOOOOOOOOOOOOOOOOOOWO
5 5
OOOOO
OOOOO
OXXOO
OWXCO
OOXOOSample Output
#notworth
8
Comments
I think that there are cases where you can't even reach the washroom because I indexofbounds when I used an ArrayList but AC without one.
https://dmoj.ca/problem/ccc08s3
can someone help me in understanding what is the issue with my code? (thx a lot btw)
You may seriously consider joining the DMOJ Discord for help.
thx
Real gamers don't pee 😎
Why is my program taking so long? The problem seems to be the bfs. I used a kind of adjacency matrix to store the edges. Could that be the reason it's taking so long?
You're checking for way too many things. Just store the map in a 2D character array and traverse the map from C to W.
Drop the
ok_tileand only check if the next tile you're going to is within the boundaries of the map and that the next tile is not a X.Thanks! idk why I tried it that way
This comment is hidden due to too much negative feedback. Show it anyway.
5000 cases? can you solve 5000 cases in under 13 seconds?
The expected time complexity should be along the lines of
which comes out to 
, which is definitely passable in a much smaller time limit. The fastest solutions in C++ pass the largest cases in under half a second. Of course, this would be different in other languages, but 13 seconds is actually much more than necessary. Even a proper Python solution (in PyPy) shouldn't require more than 5 seconds at most.
it's 13 seconds per test case
It's 13 seconds per case, and each case can contain up to 5000 different scenarios. So you need to compute up to 5000 scenarios of this question within 13 seconds.
1 test case = 5000 cases/scenarios technically
if
then there will be 2 different grids to solve.
Wait that's how it works right? or am I misunderstanding something?
Is it guaranteed that there is both a washroom and a computer in the house?
"The next w lines will contain l characters, each one of the following"
That just means that each input will be one of the four, and no other random characters. It doesn't confirm that there will always be both a washroom and a computer in the house. But I AC'd anyways so it doesn't matter now.
It is possible for the washroom to be not reachable from the computer. What kind of house has the washroom disconnected from the rest of the rooms?
Houses that are
#notworthto live in.This comment is hidden due to too much negative feedback. Show it anyway.
My submission seems to be too slow or inefficient for the last test case, are there any better algorithms I can implement to improve processing speed? Thank you!
Use BFS, right now you are just filling in an array rather than trying to find the shortest path to W.
For some reason when I read from stdin.readline() I get WA when I get AC for input(). Can someone explain why this is?
sys.stdin.readlinereturns the string with a\nat the end.