Unique Paths with Obstacles

You are given an m x n grid where each cell is either 0 (an empty space) or 1 (an obstacle). Your task is to determine 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 point in time, and you cannot step on an obstacle.

The problem can be formulated using dynamic programming where the number of ways to reach a cell is the sum of ways to reach the cell from above and from the left, if the cell is not blocked. If the starting cell itself is blocked, then no path exists.

The formula for a cell (i, j) is given in \( \LaTeX \) as:

\[ \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} \]

Output the number of unique paths from the top-left to the bottom-right that avoid obstacles.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains two space-separated integers m and n, where m is the number of rows and n is the number of columns.
• This is followed by m lines, each containing n space-separated integers (either 0 or 1) representing the grid. Here, 0 indicates an empty cell and 1 indicates an obstacle.

outputFormat

The output is a single integer printed to standard output (stdout) that represents the number of unique paths from the top-left corner to the bottom-right corner while avoiding obstacles.

## sample

3 3
0 0 0
0 0 0
0 0 0

6