HCI '16 - Oversleep

View as PDF

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

Authors:
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 by , 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, , and . The next lines will contain characters each, one of ., X, s or e.

Output

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

Sample Input 1

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

Sample Output 1

5

Sample Input 2

3 4
XXXe
....
sXXX

Sample Output 2

4

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

bruh why is the input height by width.

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

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

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

• commented on June 9, 2020, 1:33 a.m. edit 3

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

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

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

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