Oversleep

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 32M

Authors:
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

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.

Limits

1 < n,m \le 1000

Sample Input 1

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

Sample Output 1

5

Sample Input 2

3 4
XXXe
....
sXXX

Sample Output 2

4

Comments


  • -5
    nathancoulas2003  commented on June 9, 2020, 9:34 p.m. edit 2

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


  • 2
    Mystical  commented on June 8, 2020, 7:59 p.m.

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


    • 3
      Dingledooper  commented on June 8, 2020, 9:16 p.m.

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


      • -5
        Mystical  commented on June 8, 2020, 9:33 p.m. edit 3

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


        • 5
          Dingledooper  commented on June 8, 2020, 10:35 p.m.

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


        • -2
          Togohogo1  commented on June 8, 2020, 10:35 p.m.

          Testing your code for AC


          • -2
            Mystical  commented on June 8, 2020, 10:49 p.m.

            Oh ok.


  • 3
    max  commented on Jan. 6, 2018, 12:43 a.m. edit 3

    How come C is disabled for this question?


    • 3
      Neon  commented on Jan. 29, 2020, 12:47 p.m.

      its not.