Shortest Path
Time: 1.0 s Memory: 1024 MB
-
You are given a maze represented as a grid where . is a traversable cell and # is a wall. The starting cell is marked with an S and the goal is marked with a G. Your task is to calculate the length of the shortest path from the starting cell to the goal without going through walls.
Input
The first line contains two integers $N$ and $M$ ($3 \leq N,M \leq 10$), the height and width of the maze. The following $N$ lines describe the maze. Each line contain a string of length $M$. It’s guaranteed that the edges of the maze are walls and that there is exactly one start and one goal.
Output
Output a single integer: the minimum number of horizontal and vertical steps required to go from the start to the goal without stepping on a wall.
Sample Input 1 Sample Output 1 6 10 ########## #.....G..# #######..# #.S..#...# #......#.# ##########
10
Sample Input 2 Sample Output 2 5 8 ######## #....G.# ####.#.# #.S.#..# ########
-1
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - Shortest Path