Unique Paths with Obstacles

You are given a grid of size \(m \times n\) where each cell is either free (0) or contains an obstacle (1). The robot starts at the top-left cell (\(0,0\)) and needs to reach the bottom-right cell (\(m-1, n-1\)). The robot can only move either down or right at any point in time. Determine the number of unique paths from the start to the destination while avoiding obstacles. Note that if the starting cell or the destination cell is an obstacle, the number of unique paths is 0.

The recurrence relation for the dynamic programming solution 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} ]

with the initialization \(dp[0][0] = 1\) if \(grid[0][0] = 0\) (i.e., not an obstacle).

inputFormat

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

outputFormat

Output a single integer, which is the number of unique paths from the top-left corner to the bottom-right corner of the grid.

3 3
0 0 0
0 1 0
0 0 0

2