Minimum Steps in a Grid

You are given a grid with dimensions \( m \times n \). Each cell in the grid is either open or blocked, represented by . (open) and # (blocked) respectively. Your task is to determine the minimum number of steps required to travel from the top-left cell at \( (0,0) \) to the bottom-right cell \( (m-1,n-1) \). The movement is restricted to the four cardinal directions: up, down, left, and right. If a path does not exist, the output should be \(-1\).

Note: The number of steps is counted as the number of moves between adjacent cells. For example, if the starting cell is the same as the ending cell (i.e. a grid of size 1×1 and it is not blocked), the answer is 0.

The problem can be modeled as finding the shortest path in an unweighted grid where obstacles prevent passage. A common approach is to use a Breadth-First Search (BFS) algorithm.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains two space-separated integers \( m \) and \( n \), representing the number of rows and columns of the grid.
• The following \( m \) lines each contain a string of length \( n \) consisting of the characters . and #, representing the grid. There are no spaces between the characters.

For example:

3 3
.##
.#.
...

outputFormat

The output should be written to stdout as a single integer — the minimum number of steps required to reach the bottom-right cell from the top-left cell using valid moves. If it is impossible to reach the destination, output \(-1\).

3 3
.##
.#.
...

4