Unique Paths in a Grid with Obstacles

Given an n × m grid where each cell is either empty (0) or an obstacle (1), your task is to determine the number of unique paths from the top-left corner to the bottom-right corner. You are only allowed to move either right or down at any step.

If the starting cell (top-left) or the destination cell (bottom-right) is an obstacle, the answer is 0.

The state transition equation for a cell \( (i,j) \) that is not an obstacle is given by:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

where \( dp[i][j] \) denotes the number of unique paths to cell \( (i,j) \) from the start.

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space, indicating the number of rows and columns respectively. The next \( n \) lines each contain \( m \) integers (either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer representing 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