Unique Paths in Grid with Obstacles

You are given a grid with N rows and M columns. Each cell of the grid is either an open cell denoted by . or an obstacle denoted by #. Your task is to calculate the number of unique paths from the top-left corner to the bottom-right corner of the grid.

In moving from one cell to another, you can only move either down or right. If the starting cell (1,1) or the ending cell (N,M) is an obstacle (i.e. #), then no valid path exists.

The recurrence relation for the number of ways to reach a cell (i, j) (assuming there is no obstacle at that cell) is given by:

[ 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 starting cell is initialized as dp[0][0] = 1 if it is not an obstacle.

inputFormat

The first line contains two integers N and M separated by a space representing the number of rows and columns respectively.

The next N lines each contain a string of length M consisting of characters . (empty cell) and # (obstacle) representing the grid.

outputFormat

Output a single integer denoting the number of unique paths from the top-left to the bottom-right corner of the grid.

3 3
...
.#.
...

2