Unique Paths in a Grid with Obstacles

You are given a rectangular grid of size \(n \times m\). Each cell in the grid is either empty (represented by a dot '.') or blocked (represented by a hash '#'). Your task is to find the number of unique paths from the top-left cell (first row, first column) to the bottom-right cell (last row, last column). You can only move right or down at any step, and you cannot move through blocked cells.

Note: The starting cell and the ending cell are guaranteed to be accessible (i.e. they will always be '.').

The movement is restricted to two directions:

• Right
• Down

Solve the problem using dynamic programming. The recurrence relation for the number of ways \(dp[i][j]\) is given by:

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

Your final answer is \(dp[n-1][m-1]\), which is the number of unique paths to reach the bottom-right cell.

inputFormat

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

Each of the following \(n\) lines contains a string of \(m\) characters, each character being either '.' (empty) or '#' (blocked), representing the grid.

outputFormat

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

## sample

3 3
...
.#.
...

2