Unique Paths in a Grid with Obstacles

You are given a grid of size M x N represented as a matrix with values 0 and 1, where 0 indicates an empty cell and 1 indicates an obstacle. Your task is to calculate the number of unique paths from the top-left corner (starting cell) to the bottom-right corner (destination) of the grid. You may only move either right or down at any point in time.

Note: If either the starting cell or the destination cell is blocked (has value 1), then there is no valid path.

The problem requires you to implement a solution that takes input from standard input (stdin) and outputs the result to standard output (stdout).

The number of unique paths is computed using dynamic programming where each cell contains the count of ways to get to that cell from the start.

The recurrence relation can be written in LaTeX as:

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

inputFormat

The first line contains two integers M and N separated by space indicating the number of rows and columns of the grid, respectively. The following M lines each contain N space-separated integers where each integer is either 0 or 1 representing an empty cell or an obstacle.

outputFormat

Output a single integer that represents 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