Unique Paths in a Grid with Obstacles

You are given a grid represented as a 2D matrix with 0 and 1 values. A cell marked with 0 indicates a free space, whereas a cell marked with 1 represents an obstacle.

Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either downward or rightward at any point in time.

If either the starting or ending cell is blocked (i.e. has a value of 1), the result should be 0.

The solution can be derived using dynamic programming. In mathematical terms, if we let \(dp[i][j]\) represent the number of ways to reach cell \((i, j)\) then the state transition is:

\[ \begin{align*} dp[i][j] &= \begin{cases} dp[i-1][j] + dp[i][j-1] & \text{if } matrix[i][j]=0, \\ 0 & \text{if } matrix[i][j]=1. \end{cases} \end{align*} \]

inputFormat

The input is read from stdin and has the following format:

• The first line contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns of the grid respectively.
• The next \(n\) lines each contain \(m\) space-separated integers (each integer is either 0 or 1) representing the grid.

outputFormat

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

## sample

3 3
0 0 0
0 1 0
0 0 0

2