Unique Paths with Obstacles

You are given an m × n grid, where each cell is either empty (0) or contains an obstacle (1). Your task is to compute 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, and you cannot pass through cells containing obstacles.

The problem can be defined with the recurrence relation:

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

with the base condition \(dp[0][0] = 1\) if the starting cell is not blocked. If the starting or ending cell is blocked, the answer is 0.

It is guaranteed that the grid dimensions and cell values will be provided in such a way that a solution exists within the constraints.

inputFormat

The first line of the input contains 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) that represent the grid.

outputFormat

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

3 3
0 0 0
0 0 0
0 0 0

6