Grid Pathfinding with Boulders

You are given a grid of size \(n \times m\). Each cell is either empty (denoted by a .) or contains a boulder (denoted by a #). Starting from the top-left cell, your task is to determine the minimum number of moves required to reach the bottom-right cell. You can move in the four cardinal directions: up, down, left, or right, and you cannot move into cells containing boulders. If a valid path does not exist, output \(-1\).

Note: The first cell (top-left) and the last cell (bottom-right) will always be within the grid; however, if either of these cells contains a boulder, the answer is immediately \(-1\). The moves are counted as steps between adjacent cells.

inputFormat

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

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the grid, respectively.
2. The following \(n\) lines each contains a string of length \(m\) consisting of characters . (empty cell) or # (boulder) representing the grid.

outputFormat

Output a single integer to stdout: the minimum number of moves needed to reach the bottom-right cell from the top-left cell, or \(-1\) if no such path exists.

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

8