Unique Paths with Obstacles

You are given a grid of size \(n \times m\) where some cells are blocked (represented by 1) and others are free (represented by 0). Your task is to compute the number of unique paths from the top-left cell (start) to the bottom-right cell (destination) by moving only to the right or down.

If either the starting cell or the destination cell is blocked, then no path exists. This problem can be solved using dynamic programming. In particular, define \(dp[i][j]\) as the number of ways to reach cell \((i, j)\). Then, for a free cell, the recurrence is given by:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

where the unreachable cells (or blocked cells) contribute 0 paths. Using this recurrence, compute the result for the given grid.

inputFormat

The first line of input contains two space-separated integers \(n\) and \(m\) — the number of rows and columns of the grid respectively. Each of the next \(n\) lines contains \(m\) integers, each either 0 or 1, indicating a free cell or blocked cell respectively.

Input is read from standard input (stdin).

outputFormat

Output a single integer representing the number of unique paths from the start (top-left cell) to the destination (bottom-right cell). The result should be printed to standard output (stdout).

3 3
0 0 0
0 1 0
0 0 0

2