Maze Shortest Path

Given a maze represented by a grid of n rows and m columns, where each cell is either passable ('.') or blocked ('#'), find the shortest path from the top-left cell (entrance) to the bottom-right cell (exit). Movement is allowed in four directions: up, down, left, and right. If there is no valid path from the entrance to the exit, output -1.

The first line of the input consists of two integers, n and m, denoting the number of rows and columns respectively. The following n lines each contain a string of length m representing a row of the maze.

The answer is the number of steps on the shortest path from the entrance to the exit. Note that the start and end positions are not counted as separate moves; rather, the step count increases with each move from one cell to an adjacent cell.

The solution should use an appropriate breadth-first search (BFS) to guarantee the discovery of the shortest route if one exists.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
row1
row2
...
rown

Where n and m are integers representing the number of rows and columns of the maze respectively, and each row is a string of length m consisting only of the characters '.' and '#' .

outputFormat

Output the length of the shortest path from the top-left corner to the bottom-right corner on a single line via standard output (stdout). If there is no valid path, output -1.

5 5
.....
.#.#.
.#.#.
.#.#.
.....

8