Unique Paths with Obstacles

You are given a grid of size m × n where each cell is either open (0) or blocked (1). The task is to determine the number of unique paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (m-1, n-1)). At any point, you can only move either down or right. If either the starting cell or the destination cell is blocked, then there are no valid paths.

The dynamic programming recurrence used is:

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

with the proper boundary conditions and ensuring that no paths go through cells with obstacles.

inputFormat

The input is provided via standard input (stdin). The first line contains two integers m and n representing the dimensions of the grid. This is followed by m lines, each containing n integers (either 0 or 1) separated by spaces, representing 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.## sample

3 3
0 0 0
0 0 0
0 0 0

6