Unique Paths with Obstacles

You are given an m x n grid representing a map where some cells are obstacles and some are free. The grid is represented as a two-dimensional array where 0 indicates a free cell and 1 indicates an obstacle.

Your task is to compute the number of unique paths from the top-left cell (first cell) to the bottom-right cell (last cell) of the grid. You can only move either right or down at any point in time.

If either the start or the destination cell is an obstacle, then there is no valid path. The answer must be computed using dynamic programming. In mathematical terms, the recurrence relation is given by:

\[ \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 } (\text{with appropriate boundary conditions}). \end{cases} \]

Compute and output the number of unique paths from the top-left corner to the bottom-right corner.

inputFormat

The input is given via standard input (stdin). The first line contains two integers m and n, which represent the number of rows and columns in the grid, respectively. This is followed by m lines, each containing n space-separated integers (each integer is either 0 or 1) 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 of the grid.

3 3
0 0 0
0 1 0
0 0 0

2