Minimum Steps to Reach End in a Grid

You are given a grid with M rows and N columns. Each cell in the grid is either a clear cell denoted by . or an obstacle denoted by #. Your task is to compute the minimum number of steps required to travel from the top-left cell at position (0,0) to the bottom-right cell at position (M-1, N-1) by moving only in the four cardinal directions (up, down, left, right).

If either the starting cell or the destination cell is blocked (i.e. contains a #), then the answer is -1. Otherwise, a valid path might or might not exist.

The problem can be modeled as a breadth-first search (BFS) problem in an unweighted grid. Formally, you need to find the minimum number of steps s such that there exists a sequence of moves satisfying \[ (x_0, y_0) \to (x_1, y_1) \to \cdots \to (x_s, y_s), \] where (x_0, y_0) = (0, 0), (x_s, y_s) = (M-1, N-1), and each successive cell is adjacent by one of the four directions.

If no such path exists, print -1.

inputFormat

The first line contains two integers M and N separated by a space, representing the number of rows and columns, respectively.

This is followed by M lines, each containing a string of length N which represents a row of the grid. Each character is either . (clear cell) or # (obstacle).

outputFormat

Output a single integer: the minimum number of steps required to reach the bottom-right cell from the top-left cell. If such a path does not exist, output -1.

## sample

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

8

</p>