Shortest Path in a Grid

You are given a grid of size \(n \times m\) where each cell is either open (denoted by .) or blocked by an obstacle (denoted by #). Your task is to compute the minimum number of moves required to travel from the top-left cell (coordinate \((0,0)\)) to the bottom-right cell (coordinate \((n-1,m-1)\)) moving only in the four cardinal directions (up, down, left, right). If there is no valid path, output \(-1\).

The movement cost is defined as 1 per move. In an unobstructed grid the minimum steps required would be \((n-1)+(m-1)\), but obstacles may force a longer route or block the path entirely.

Note: The grid is given as \(n\) rows of \(m\) space-separated characters.

inputFormat

The input is given from standard input in the following format:

n m
row_1
row_2
... 
row_n

Here, the first line contains two integers \(n\) and \(m\) denoting the dimensions of the grid. The next \(n\) lines each contain \(m\) space-separated characters, each being either . or #.

outputFormat

Output the minimum number of steps required to go from the top-left to the bottom-right cell. If no valid path exists, output \(-1\).

3 3
. . .
. # .
. . .

4