Minimum Grass Cells Mowed

You are given a grid with N rows and M columns, where each cell is either a grass cell represented by . or a water cell represented by #. You start at the top-left cell (1,1) and your goal is to reach the bottom-right cell (N,M).

You can only move in two directions: right or down. When you move into a grass cell, you mow it. Your task is to find the minimum number of grass cells that must be mowed in order to reach the destination. If the destination cannot be reached following the movement constraints or if either the start or destination is blocked by water, output \(-1\).

The problem can be formulated as finding the shortest path in a grid with only rightward and downward moves. For a cell \((i,j)\), the only possible moves are to \((i, j+1)\) and \((i+1, j)\).

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space representing the number of rows and columns of the grid.

This is followed by \(N\) lines, each containing a string of length \(M\). Each character is either . (grass) or # (water).

outputFormat

Output one integer: the minimum number of grass cells mowed to reach the bottom-right corner. If there is no valid path, output \(-1\).

3 3
...
.#.
...

5