Unique Paths in a Grid with Obstacles

You are given a grid with m rows and n columns. Each cell in the grid is either open (denoted by 0) or blocked by an obstacle (denoted by 1). You need to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time.

The problem can be modeled using dynamic programming. Let \(dp[i][j]\) represent the number of ways to reach cell \((i, j)\). The recurrence relation is:

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

It is important to note that if the starting cell \(grid[0][0]\) is an obstacle, then there is no valid path.

inputFormat

The input begins with two integers \(m\) and \(n\) representing the number of rows and columns, respectively. This is followed by \(m\) lines, each containing \(n\) space-separated integers (either 0 or 1), representing the grid. A 0 indicates an open cell, and a 1 indicates an obstacle.

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner of the grid. The answer should be printed to standard output.

3 3
0 0 0
0 1 0
0 0 0

2