Unique Paths in Grid with Obstacles

You are given an m x n grid represented by m lines each containing n characters. Each character is either a '.' representing an empty cell or a '#' representing an obstacle. You start at the top left cell and need to reach the bottom right cell. At each step, you can only move either right or down.

The number of unique paths can be computed using dynamic programming. Define \(dp[i][j]\) as the number of unique ways to get to cell \((i,j)\). The recurrence is defined as follows:

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

with the initial condition \(dp[0][0] = 1\) if the starting cell is not blocked. If either the start or the destination is blocked, the answer is 0.

inputFormat

The first line contains two space-separated integers, m and n, which represent the number of rows and columns in the grid, respectively.

This is followed by m lines, each containing a string of n characters. Each character is either '.' (free cell) or '#' (obstacle).

outputFormat

Output a single integer representing the number of unique paths from the top left to the bottom right of the grid, following the movement constraints.

## sample

3 3
...
...
...

6