Unique Paths with Obstacles

You are given a grid with obstacles, represented as a matrix of integers. A cell with a value of 0 indicates an empty cell, and a cell with a value of 1 indicates an obstacle. Starting from the top-left cell, you need to reach the bottom-right cell by only moving either right or down at any given step.

The problem can be formulated mathematically as follows: Given an \( m \times n \) grid, compute the number of unique paths from cell \( (0,0) \) to \( (m-1,n-1) \) avoiding the obstacles. Use dynamic programming where, if \( dp[i][j] \) represents the number of ways to reach cell \( (i,j) \), then for cells without obstacles the recurrence is:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \) (if the cell is not an obstacle).

If either the start or the destination cell contains an obstacle, then the answer is 0. The task is to compute and output the number of such unique paths.

inputFormat

The input is given from 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. A value of 0 indicates an empty cell, while 1 indicates an obstacle.

outputFormat

Output to stdout a single integer that indicates the number of unique paths from the top-left to the bottom-right corner of the grid, avoiding obstacles. If no valid path exists, output 0.## sample

3 3
0 0 0
0 1 0
0 0 0

2