Shortest Path in a Grid

You are given a grid with n rows and m columns. Each cell is either a road (.) or a building (#). Your task is to compute the length of the shortest path from the top-left corner (cell [0, 0]) to the bottom-right corner (cell [n-1, m-1]) by moving only up, down, left, or right. You can only travel on cells representing roads (.).

If the start cell or the destination cell is blocked (i.e. marked with #), or if no such path exists, output -1. Otherwise, output the minimum number of moves required to reach the destination.

The length of the path is defined as the number of moves taken. Note that if the starting cell is the same as the destination (i.e. a 1x1 grid with a road), the answer is 0.

The underlying algorithm to solve this problem is Breadth-First Search (BFS), which guarantees the shortest path if one exists.

inputFormat

The first line contains two integers n and m separated by a space, denoting the number of rows and columns in the grid, respectively.

The next n lines each contain m space-separated characters. Each character is either . representing a road or # representing a building.

outputFormat

Output a single integer to stdout: the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output -1.

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

8