Unique Paths With Obstacles

You are given an \( m \times n \) grid represented by integers, where 0 indicates an empty cell and 1 indicates an obstacle. Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner, moving only right or down, while avoiding obstacles.

If the starting cell or the destination cell has an obstacle, then there is no valid path. The recurrence relation used in dynamic programming is given by:

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

provided that cell \((i,j)\) is not an obstacle. Otherwise, \(dp[i][j] = 0\).

inputFormat

The input is read from standard input (stdin). The first line 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 (0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout) which represents the number of unique paths from the top-left to the bottom-right corner of the grid.

3 3
0 0 0
0 0 0
0 0 0

6