DMOPC '13 Contest 1 P4 - AFK

View as PDF

Points: 12 (partial)
Time limit: 13.0s
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

Kids 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 by 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:

• O is open space (you can pass through these)
• X is wall (you can't pass through these)
• C is computer (this is where you start)
• W is washroom (this is where you want to go)

Sample Input

2
27 5
OOCOOOOOOOOOOOOOOOOOOOOOOOO
XXXXXXXXXXXXXXXXXXXXXXXXXXO
OOOOOOOOOOOOOOOOOOOOOOOOOOO
OXXXXXXXXXXXXXXXXXXXXXXXXXX
OOOOOOOOOOOOOOOOOOOOOOOOOWO
5 5
OOOOO
OOOOO
OXXOO
OWXCO
OOXOO

Sample Output

#notworth
8

• commented on June 28, 2020, 12:20 p.m.

can someone help me in understanding what is the issue with my code? (thx a lot btw)

• commented on June 28, 2020, 12:41 p.m.

You may seriously consider joining the DMOJ Slack for help. https://slack.dmoj.ca/

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

thx

• commented on April 17, 2020, 12:20 p.m.

Real gamers don't pee 😎

• commented on June 28, 2019, 1:08 p.m. edited

Last test case took 29.788 seconds c; (with PY3, later did PYPY3 and it did it in 6 seconds o_o)

• commented on July 4, 2018, 2:30 p.m.

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?

• commented on July 4, 2018, 4:42 p.m.

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_tile and 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.

• commented on July 5, 2018, 2:52 p.m.

Thanks! idk why I tried it that way

• commented on Jan. 24, 2018, 8:23 a.m.

is it possible that in a house can be 2 'C' or more or 2'W' or more ???

• commented on Aug. 6, 2017, 11:45 p.m.

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

• commented on April 3, 2018, 1:23 p.m.

5000 cases? can you solve 5000 cases in under 30 seconds?

• commented on April 3, 2018, 4:19 p.m.

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 30 seconds is actually much more than necessary. Even a proper python solution (in pypy) shouldn't require more than 5-10 seconds at most.

• commented on April 3, 2018, 2:51 p.m.

it's 30 seconds per test case

• commented on June 1, 2018, 10:48 a.m. edit 2

It's 30 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 30 seconds.

1 test case = 5000 cases/scenarios technically

if t = 2 then there will be 2 different grids to solve.

Wait that's how it works right? or am I misunderstanding something?

• commented on June 8, 2017, 8:40 p.m.

Is it guaranteed that there is both a washroom and a computer in the house?

• commented on June 8, 2017, 11:17 p.m.

"The next w lines will contain l characters, each one of the following"

• commented on June 9, 2017, 4:26 p.m.

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.

• commented on Nov. 22, 2016, 4:43 p.m.

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?

• commented on Nov. 22, 2016, 5:37 p.m.

Houses that are #notworth to live in.

• commented on July 26, 2017, 10:47 a.m.

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

• commented on Nov. 21, 2016, 5:15 p.m. edited

NEVERMIND

• commented on Feb. 25, 2016, 10:11 p.m.

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!

• commented on Feb. 26, 2016, 8:40 a.m.

Use BFS, right now you are just filling in an array rather than trying to find the shortest path to W.

• commented on Jan. 16, 2015, 9:05 p.m.

For some reason when I read from stdin.readline() I get WA when I get AC for input(). Can someone explain why this is?

• commented on Jan. 16, 2015, 9:18 p.m.

sys.stdin.readline returns the string with a \n at the end.