Submit solution

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
```

## Comments

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

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

thx

Real gamers don't pee 😎

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

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_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.Thanks! idk why I tried it that way

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

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

5000 cases? can you solve 5000 cases in under 30 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 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.

it's 30 seconds per test case

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

technicallyif t = 2 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,

eachone 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

`#notworth`

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

NEVERMIND

Take a look at https://dmoj.ca/about/codes/

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.readline`

returns the string with a`\n`

at the end.