Unique Paths in a Grid with Obstacles

You are given a two-dimensional grid of size \(m \times n\) filled with integers 0 and 1, where 0 represents a free cell and 1 represents an obstacle. Your task is to compute the number of unique paths from the top-left corner (cell \((1,1)\)) to the bottom-right corner (cell \((m,n)\)), moving only right or down, and avoiding obstacles. If there is no valid path, return 0.

Note: The starting and ending cells are always considered, but if the starting cell is an obstacle, then the answer is 0.

The problem can be solved using dynamic programming. In particular, let \(dp[i][j]\) denote the number of unique paths to cell \((i,j)\) from the start. The transition is given by:

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

Your task is to implement a solution that reads the grid from standard input and outputs the number of unique paths to standard output.

inputFormat

The input is read from stdin in the following format:

• The first line contains two space-separated integers \(m\) and \(n\) representing the number of rows and columns of the grid.
• The following \(m\) lines each contain \(n\) space-separated integers (either 0 or 1) that represent the grid cells.

outputFormat

Output a single integer to stdout indicating the number of unique paths from the top-left to the bottom-right cell, while avoiding obstacles.

3 3
0 0 0
0 1 0
0 0 0

2