Unique Paths in a Grid with Obstacles

You are given an m x n grid where some of the cells are obstacles. The obstacles are denoted by 1 and the empty spaces by 0. Your task is to find the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)). You can only move either down or right at any step.

Dynamic Programming Approach:

If we denote \(dp[i][j]\) as the number of unique paths to reach cell \((i, j)\), then for cells that are not obstacles, the relation is:

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

If the starting cell is an obstacle, then no path exists. Similarly, if any cell is an obstacle, it contributes 0 paths.

This problem requires careful handling of grid boundaries and obstacles. Consider using a 2D dynamic programming table to store intermediate results.

inputFormat

The first line contains two integers, m and n, representing the number of rows and columns respectively. The next m lines each contain n space-separated integers (either 0 or 1) which represent the grid cells.

outputFormat

Print a single integer which is the number of unique paths from the top-left corner to the bottom-right corner of the grid.## sample

3 3
0 0 0
0 0 0
0 0 0

6