Unique Paths in a Grid with Obstacles

You are given a grid of size \(m \times n\) where each cell contains either a 0 or a 1. A cell with 0 means it is free to walk, and a cell with 1 represents an obstacle. Your task is to calculate the number of unique paths that lead from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)), moving only down or right at any step.

Movement constraints:

• You may only move either down or right.
• You cannot move through an obstacle.

Note: If the starting cell or the destination cell has an obstacle, then no valid path exists.

The answer should be computed using dynamic programming. The recurrence relation used is:

[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1, \ (dp[i-1][j] + dp[i][j-1]), & \text{otherwise.} \end{cases} ]

where dp[i][j] represents the number of unique paths to cell \((i+1, j+1)\). The answer is found at dp[m-1][n-1].

inputFormat

The input is provided via stdin in the following format:

m n
row1
row2
... 
row_m

Where:

• The first line contains two integers \(m\) and \(n\) representing the number of rows and columns of the grid.
• Each of the next \(m\) lines contains \(n\) integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer to stdout representing the number of unique paths from the top-left to the bottom-right of the grid.

## sample

3 3
0 0 0
0 0 0
0 0 0

6