Unique Paths in a Grid with Obstacles

You are given a grid of size (m \times n) consisting of integers 0 and 1. Here, 0 represents an empty cell and 1 represents an obstacle. Your task is to compute the number of unique paths from the top-left corner (cell ((0,0))) to the bottom-right corner (cell ((m-1,n-1))). You can only move either right or down at any point in time, and you cannot pass through cells that contain obstacles.

If the starting cell or the destination cell has an obstacle, then the answer is 0.

The transition function for dynamic programming can be formulated as follows:
[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1, \ (dp[i-1][j] + dp[i][j-1]), & \text{if } grid[i][j] = 0 \end{cases} ] with the base condition (dp[0][0] = 1) (if (grid[0][0] = 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 of the grid, respectively. Each of the following (m) lines contains (n) space-separated integers (either 0 or 1) defining the grid.

outputFormat

Output a single integer to standard output (stdout) representing the number of unique paths from the top-left corner to the bottom-right corner. If there is no valid path, output 0.## sample

3 3
0 0 0
0 1 0
0 0 0

2