Unique Paths in a Grid with Obstacles

You are given a grid of size \( n \times m \) where each cell contains either a 0 or a 1. A cell with a 0 indicates a free cell, and a cell with a 1 indicates 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 down or right at any step. If either the starting cell or the destination cell is blocked, the answer is 0.

The number of unique paths can be computed using dynamic programming with the following recurrence:

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

Note: Consider \( dp(0,0)=1 \) if the starting cell is free.

inputFormat

The input is given via standard input (stdin). The first line contains two integers \( n \) and \( m \) representing the number of rows and columns respectively. The following \( n \) lines each contain \( m \) integers (either 0 or 1) separated by spaces, describing the grid.

outputFormat

Output a single integer via standard output (stdout) representing the number of unique paths from the top-left corner to the bottom-right corner.

3 3
0 0 0
0 1 0
0 0 0

2