Unique Paths on a Grid with Obstacles

You are given an n × m grid representing a map. Each cell in the grid is either passable ('.') or blocked ('#'). Starting at the top-left corner (cell (0,0)) and moving only right or down, your task is to determine the number of distinct paths to reach the bottom-right corner (cell (n-1, m-1)).

If the starting or ending cell is blocked, the answer is immediately 0. Otherwise, the answer can be computed using dynamic programming with the recurrence relation in LaTeX as follows:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

where \(dp[i][j]\) represents the number of ways to reach cell \((i, j)\). The initial condition is \(dp[0][0]=1\) if the starting cell is not blocked.

inputFormat

The first line contains two integers n and m separated by a space, representing the number of rows and columns in the grid respectively.

Each of the next n lines contains a string of length m composed of characters '.' and '#' where '.' indicates a free cell and '#' indicates an obstacle.

outputFormat

Output a single integer: the number of distinct paths from the top-left corner to the bottom-right corner following the described rules.

3 3
...
.#.
...

2