Unique Paths in a Grid with Obstacles

You are given a grid represented as an n x m matrix where each cell is either 0 (empty) or 1 (obstacle). Your task is to count 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 right or down at each step.

If the starting or the destination cell is blocked (i.e. contains 1), then there is no valid path and you should output 0.

The problem can be solved 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{otherwise} \end{cases}\)

The final answer is \(dp[n-1][m-1]\).

inputFormat

The first line contains two integers n and m representing the number of rows and columns. Each of the next n lines contains m integers (0 or 1), which denote the grid cells.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2