Counting Valid Paths in a Grid with Obstacles

You are given an \(n \times m\) grid where each cell is either free (denoted by '.') or blocked by an obstacle (denoted by '#'). Your task is to count the number of distinct valid paths from the top-left cell (position \( (0, 0) \)) to the bottom-right cell (position \( (n-1, m-1) \)).

In each step, you are allowed to move either right or down. A path is valid if it does not visit any cell containing an obstacle. Note that if the starting cell or the ending cell is blocked, the answer is \(0\).

Formally, if we define \(dp[i][j]\) as the number of ways to reach cell \((i,j)\), then the recurrence is given by:

\[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \\ dp[i-1][j] + dp[i][j-1], & \text{otherwise, with appropriate boundary conditions.} \end{cases} \]

Calculate \(dp[n-1][m-1]\) for the answer.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers \(n\) and \(m\), representing the number of rows and columns respectively.
2. The next \(n\) lines each contain a string of length \(m\) made up of the characters '.' and '#', representing the grid.

outputFormat

Output a single integer to stdout which is the number of distinct valid paths from the top-left to the bottom-right cell. If no valid path exists, output \(0\).

3 3
...
.#.
...

2