Distinct Paths in a Grid with Obstacles

You are given a grid with ( n ) rows and ( m ) columns. Each cell in the grid is either an open space denoted by a period (.) or an obstacle denoted by a hash (#). Your task is to compute the number of distinct paths from the top-left cell (cell ( (1,1) )) to the bottom-right cell (cell ( (n,m) )). You are only allowed to move either down or right at any step. If the starting or ending cell is blocked, there is no valid path.

The problem can be formally stated as follows:

Given a grid ( G ) of size ( n \times m ) where ( G_{i,j} \in {'.', '#'} ), find the number of ways to reach ( G_{n,m} ) from ( G_{1,1} ) by moving only down or right, while avoiding obstacles.

The answer should be computed using dynamic programming, where the recurrence relation is given by: [ \text{dp}[i][j] = \begin{cases} 0 & \text{if } G_{i,j} = '#' \ \text{dp}[i-1][j] + \text{dp}[i][j-1] & \text{otherwise} \end{cases} ]

with ( \text{dp}[1][1] = 1 ) (provided ( G_{1,1} ) is not an obstacle).

inputFormat

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

• The first line contains two integers ( n ) and ( m ) — the number of rows and the number of columns in the grid.
• The next ( n ) lines each contain a string of length ( m ) consisting of characters . and #, representing the grid.

outputFormat

Output the number of distinct paths from the top-left to the bottom-right cell. The output should be written to standard output (stdout).## sample

3 3
...
.#.
...

2