HCI '16 - Oversleep

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 0.6s
Memory limit: 32M
Authors:
zj97, damian, fanpu
Problem type

Yi Kai has overslept and realized that he has very little time left to attend a very important event! Having recently moved, he takes out a map to navigate through his new neighbourhood to reach his destination. The map shows that the neighbourhood is arranged in a grid of size n by m, with a . indicating a walkable path which takes 1 minute to walk across, and an X indicating a building. He takes out his marker, looks around his surroundings, and marks his current position with an s on the map. Then, he finds his destination, and marks an e on it. He looks at the map again, but the number of possible routes to his destination overwhelms him! Help Yi Kai find out how much time he will need to reach his destination if he uses the shortest possible route!

(Inspired by Yi Kai oversleeping before previous NOI trainings)

Input

The first line will contain two integers, n, and m. The next n lines will contain m characters each, one of ., X, s or e.

Output

A single integer, the minimum time he requires to reach his destination in minutes, or -1 if it is not possible and he has to call for a helicopter.

Constraints

1 < n,m \le 1\,000

Sample Input 1

4 4
s...
....
....
...e

Sample Output 1

5

Sample Input 2

3 4
XXXe
....
sXXX

Sample Output 2

4

Comments


  • -2
    Xiang_li  commented on July 17, 2021, 2:01 p.m.

    bruh why is the input height by width.


  • 0
    Mystical  commented on June 8, 2020, 11:59 p.m.

    How am I getting TLE with BFS? (https://dmoj.ca/src/2135683) Am I missing something?


    • 3
      Dingledooper  commented on June 9, 2020, 1:16 a.m.

      g[x][y] = 'X' should be g[y][x] = 'X'.


      • -10
        Mystical  commented on June 9, 2020, 1:33 a.m. ← edit 3

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


        • 11
          Dingledooper  commented on June 9, 2020, 2:35 a.m.

          Uh, to figure out the issue with your code...


        • 0
          Togohogo1  commented on June 9, 2020, 2:35 a.m.

          Testing your code for AC


          • -5
            Mystical  commented on June 9, 2020, 2:49 a.m.

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