Unique Paths in a Grid with Obstacles

You are given a grid of size m x n where each cell contains either a 0 (an empty cell) or a 1 (an obstacle). Your task is to count the number of unique paths from the top-left corner to the bottom-right corner of the grid, if the robot can only move either right or down. Note that if the starting cell or the ending cell is an obstacle, there is no valid path.

The problem can be modeled using dynamic programming. Let \(dp[i][j]\) represent the number of ways to reach cell \((i,j)\). The recurrence relation is:

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

Be sure to handle edge cases such as grids with obstacles blocking the start or the finish, as well as small grids.

inputFormat

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

outputFormat

Output a single integer denoting the number of unique paths from the top-left corner to the bottom-right corner moving only right or down.## sample

3 3
0 0 0
0 1 0
0 0 0

2