Unique Paths with Obstacles

Given a grid of size \(M \times N\), where each cell contains either a 0 or a 1, compute the number of unique paths from the top-left corner to the bottom-right corner. A 0 represents a free cell while a 1 represents an obstacle. You can only move either down or right at any point in time.

Note: If the starting or ending cell is an obstacle, then there is no valid path, and the answer should be 0.

The problem can be solved using dynamic programming with the following recurrence relation:

[ \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.} \end{cases} ]

The initial condition is \(\text{dp}[0][0] = 1\) if the starting cell is free.

inputFormat

The first line contains two integers \(M\) and \(N\), representing the number of rows and columns of the grid.

The following \(M\) lines each contain \(N\) integers (each either 0 or 1), separated by spaces, representing the grid.

outputFormat

Output a single integer representing the number of unique paths from the top-left to the bottom-right of the grid, avoiding obstacles.

3 3
0 0 0
0 0 0
0 0 0

6