Unique Paths in a Grid

You are given an n x m grid where each cell is either . (a free cell) or # (a blocked cell). Your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner. You may only move either down or right at any step.

If either the start or destination cell is blocked, the answer is 0.

The problem can be solved by using dynamic programming. In particular, the recurrence used is given by the formula in LaTeX format below:

\(dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \\ dp[i-1][j] + dp[i][j-1], & \text{otherwise} \end{cases}\)

where \(dp[i][j]\) denotes the number of ways to reach cell \((i,j)\). The final answer is \(dp[n-1][m-1]\).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns in the grid.

Each of the next n lines contains a string of length m composed of characters . and #, representing the grid cells.

outputFormat

Output a single integer, which is the number of unique paths from the top-left corner to the bottom-right corner.

3 3
...
.#.
...

2