Unique Paths With Obstacles

You are given an m x n grid where each cell is either empty (0) or contains an obstacle (1). You need to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid, moving only right or down at any step. If the starting cell or the destination cell is an obstacle, then no path exists and the output should be 0.

This problem can be efficiently solved using dynamic programming. Let \( dp[i][j] \) be the number of ways to reach cell \( (i, j) \). The state transition is given by:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \) for \( i, j \) where the grid cell is not an obstacle. For cells that contain obstacles, \( dp[i][j] = 0 \).

Read the grid from standard input and output the computed number of unique paths to standard output.

inputFormat

The first line of input contains two integers \( m \) and \( n \) representing the number of rows and columns in the grid.

The following \( m \) lines each contain \( n \) space-separated integers (each being either 0 or 1) representing the rows of the grid.

outputFormat

Output a single integer that represents the number of unique paths from the top-left corner to the bottom-right corner of the grid.

3 3
0 0 0
0 0 0
0 0 0

6