DMOPC '13 Contest 1 P4 - AFK

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 30.0s
Memory limit: 256M

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

27 5
5 5

Sample Output



  • 0
    Cameron  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?

    • 1
      KevinLu  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.

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

        Thanks! idk why I tried it that way

  • 0
    anasschoukri2  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 ???

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

    How can you possibly TLE with 30 seconds? Why is the time limit so high?

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

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

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

        The expected time complexity should be along the lines of 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 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.

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

        it's 30 seconds per test case

        • 0
          SongJiAh  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?

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

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

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

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

      • 2
        Ninjaclasher  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.

  • 2
    xXxP0t4t0MStRxXx  commented on Nov. 22, 2016, 4:43 p.m.
    Weird floor plan

    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?

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

      Houses that are #notworth to live in.

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

        ha ha ha,very not funny

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


  • 0
    alexker  commented on Feb. 25, 2016, 10:11 p.m.
    Any Recommended Algorithms?

    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!

    • 0
      Kirito  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.

  • -1
    bobhob314  commented on Jan. 16, 2015, 9:05 p.m.
    Reading from standard input

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

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

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