Shortest Path in a Grid

You are given an n x m grid composed of walkable cells and obstacles. Each cell is represented by either a dot . (walkable) or a hash # (obstacle). Your task is to compute the shortest number of moves required to go from the top-left corner (0, 0) to the bottom-right corner (n-1, m-1) by moving in the four cardinal directions (up, down, left, right). If no valid path exists, output -1.

The distance is measured by the number of moves made. Notice that if the starting cell is blocked, then no move can be made. The solution requires a breadth-first search (BFS) over the grid.

Note: All formulas should be written in LaTeX format. For instance, the Manhattan distance can be represented as \(d = |x_2 - x_1| + |y_2 - y_1|\) but note that here we only count valid moves.

inputFormat

The input is given via standard input. The first line contains two integers, \(n\) and \(m\), representing the number of rows and columns respectively. The following \(n\) lines each contain a string of length \(m\) which represents a row of the grid. Each character is either a . (walkable cell) or a # (obstacle).

outputFormat

Output a single integer which is the shortest number of moves from the start to the goal. If no valid path exists, output -1.

3 3
...
...
...

4