Minefield Navigation: Minimum Moves Problem

You are given an N x M grid representing a minefield. Each cell in this grid is either clear (represented by .) or contains a mine (represented by *). Your task is to determine the minimum number of moves required to navigate from the top-left corner to the bottom-right corner of the grid. Moves are allowed only in the four cardinal directions (up, down, left, right) and you cannot move to a cell that contains a mine. If there is no valid path, output -1.

The problem can be mathematically described as follows:

Given a grid, find the minimum number of moves such that
\[ \text{moves} = \min_{\text{path}} \{ \text{number of steps}\} \]
subject to the condition that every visited cell \( (i,j) \) satisfies \( grid[i][j] = '.' \). If no such path exists, report \( -1 \).

This is a typical shortest path problem on a grid which can be solved using a Breadth First Search (BFS) algorithm.

inputFormat

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

• The first line contains two integers N and M (\(1 \leq N, M \leq 1000\)) representing the number of rows and columns respectively.
• The following N lines each contain a string of length M consisting only of characters . and *, representing the minefield grid.

outputFormat

Output a single integer via standard output representing the minimum number of moves required to travel from the top-left corner to the bottom-right corner. If there is no valid path, output -1.

5 5
.....
.*.*.
.*.*.
.*.*.
...*.

8