Unique Paths in a Grid with Obstacles

You are given a grid with N rows and M columns. Each cell of the grid is either 0 (an open cell) or 1 (an obstacle). Starting from the top-left corner of the grid, you need to find the number of unique paths to the bottom-right corner if you can only move either right or down at any point in time.

If the starting cell or the destination cell is an obstacle, then no path exists. Formally, if we define dp(i,j) as the number of ways to reach cell \( (i,j) \) from \( (1,1) \), the recurrence is given by:

\[ \text{dp}(i,j) = \begin{cases} 0, & \text{if } grid[i][j]=1, \\ \text{dp}(i-1,j)+\text{dp}(i,j-1), & \text{otherwise, with appropriate boundary conditions.} \end{cases} \]

Your task is to compute \( \text{dp}(N,M) \).

inputFormat

The first line contains two integers N and M separated by a space, indicating the number of rows and columns in the grid respectively. Each of the following N lines contains M integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2