DMOPC '13 Contest 1 P4 - AFK

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 13.0s
Memory limit: 256M
Author:
untitled123
Problem type

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 t (1 \le t \le 5000), where t is the number of test cases, and then followed by l and w (2 \le l, w \le 50) where l and w are the length and width, respectively, of each floor map. The next w lines will contain l 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


  • -4
    dxke02  commented on Nov. 30, 2020, 8:34 p.m.

    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.


  • 0
    professorr  commented on Oct. 12, 2020, 1:24 a.m.

    https://dmoj.ca/problem/ccc08s3


  • 0
    devnarula  commented on June 28, 2020, 4:20 p.m.

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


  • 36
    EpicChadGamer  commented on April 17, 2020, 4:20 p.m.

    Real gamers don't pee 😎


  • -2
    Cameron  commented on July 4, 2018, 6: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?


    • 2
      KevinLu  commented on July 4, 2018, 8: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.


      • 1
        Cameron  commented on July 5, 2018, 6:52 p.m.

        Thanks! idk why I tried it that way


  • -5
    Pleedoh  commented on Aug. 7, 2017, 3:45 a.m. ← edited

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


    • -1
      nikos  commented on April 3, 2018, 5:23 p.m. ← edited

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


      • 3
        aeternalis1  commented on April 3, 2018, 8:19 p.m. ← edit 3

        The expected time complexity should be along the lines of \mathcal{O}(tlw) which comes out to 5000*50*50, 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.


      • -2
        TimothyW553  commented on April 3, 2018, 6:51 p.m. ← edited

        it's 13 seconds per test case


        • 0
          SongJiAh  commented on June 1, 2018, 2:48 p.m. ← edit 3

          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 t = 2 then there will be 2 different grids to solve.

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


  • 1
    Ninjaclasher  commented on June 9, 2017, 12:40 a.m.

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


    • 0
      root  commented on June 9, 2017, 3:17 a.m.

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


      • 2
        Ninjaclasher  commented on June 9, 2017, 8: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.


  • 5
    xXxP0t4t0MStRxXx  commented on Nov. 22, 2016, 9: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?


    • 85
      Xyene  commented on Nov. 22, 2016, 10:37 p.m.

      Houses that are #notworth to live in.


      • -57
        hezeyu2007001  commented on July 26, 2017, 2:47 p.m.

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


  • 0
    alexker  commented on Feb. 26, 2016, 3:11 a.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!


    • 1
      Kirito  commented on Feb. 26, 2016, 1:40 p.m.

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


  • -4
    bobhob314  commented on Jan. 17, 2015, 2:05 a.m. ← edited

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


    • 6
      FatalEagle  commented on Jan. 17, 2015, 2:18 a.m.

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