Minimum Steps to Reach the Last Row

You are given a grid with N rows and M columns. Each cell in the grid is either accessible ('.') or blocked ('X'). You can only move to the right or down. Your task is to find the minimum number of steps required to reach any cell in the last row when starting from any cell in the first row. If it is impossible to reach the last row, output -1.

The problem can be formally defined as: given a grid G of size \( N \times M \) where \( G_{i,j} \) is either '.' or 'X', determine the minimum number of moves required such that starting from any cell in row 1 and moving only to the right (\( (0,1) \)) or down (\( (1,0) \)) you can reach any cell in row N. If there is no valid path, return -1.

inputFormat

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

• The first line contains two integers N and M separated by a space.
• The following N lines each contain a string of length M representing a row of the grid. Each character is either '.' (denoting an open cell) or 'X' (denoting a blocked cell).

outputFormat

Output a single integer to standard output: the minimum number of steps required to reach any cell in the last row from any cell in the first row. If it is impossible, output -1.

5 5
.....
..X..
...X.
X....
.....

4