Unique Paths in a Grid with Obstacles

You are given an m \times n grid where each cell is either an obstacle (represented by 1) or an empty space (represented by 0). Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner of the grid. You are only allowed to move either down or right at any step.

If the starting cell or the destination cell is blocked by an obstacle, then no valid path exists. The problem can be solved using dynamic programming. The recurrence relation 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{if } grid[i][j] = 0. \end{cases} $$

Initialize dp[0][0] = 1 if the starting cell is not an obstacle, and compute dp values for each cell accordingly. The final answer is dp[m-1][n-1].

inputFormat

The first line contains two integers m and n, separated by a space, representing the number of rows and columns in the grid, respectively. This is followed by m lines, each containing n space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner of the grid. If no such path exists, output 0.

3 3
0 0 0
0 0 0
0 0 0

6