Unique Paths with Obstacles

You are given a 2D grid of size \(m \times n\), where each cell is either 0 or 1. A value of 0 represents an empty cell and 1 represents an obstacle. You start at the top-left corner (0, 0) and want to reach the bottom-right corner (m-1, n-1). You can only move either down or right at any point in time.

Your task is to calculate the number of unique paths from the start to the destination. If the starting cell or the destination cell is blocked by an obstacle, then the answer is 0.

The state transition for the dynamic programming solution is given by:

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

where \(dp[i][j]\) is the number of unique ways to reach cell (i, j), considering that a cell with an obstacle should contribute 0 paths.

inputFormat

The first line contains two integers, \(m\) and \(n\), representing the number of rows and columns respectively.

Each of the next \(m\) lines contains \(n\) space-separated integers (either 0 or 1) that represent the grid.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2