Unique Paths in a Grid With Obstacles

You are given a 2D grid represented as an n x m matrix. Each element in the matrix is either 0 (representing an empty cell) or 1 (representing an obstacle). Your task is to calculate the number of unique paths from the top-left cell to the bottom-right cell. You can only move in two directions: right or down.

If the starting cell or the ending cell is blocked by an obstacle, then there are no valid paths and you should output 0.

The solution can be derived using dynamic programming. Let \(dp(i,j)\) be the number of ways to reach cell \((i,j)\). The recurrence relation is given by:

[ dp(i,j) = \begin{cases} 0, & \text{if } grid[i][j] = 1; \ dp(i-1,j) + dp(i,j-1), & \text{if } grid[i][j] = 0 \end{cases} ]

with initial condition \(dp(0,0)=1\) (provided that \(grid[0][0]=0\)).

inputFormat

The first line contains two integers n and m separated by a space, denoting the number of rows and columns, respectively. The following n lines each contain m space-separated integers (each 0 or 1) representing the grid.

outputFormat

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

3 3
0 0 0
0 0 0
0 0 0

6