Unique Paths in a Grid with Obstacles

This problem involves finding the number of unique paths in a 2D grid from the top-left corner to the bottom-right corner. Some cells in the grid are blocked by obstacles. A cell with value 0 represents an open cell, while a cell with value 1 represents an obstacle.

The robot can only move either down or right at any point in time. If the starting cell or the ending cell is blocked, the number of unique paths is 0.

You are required to compute the number of unique paths using dynamic programming. The state transition can be represented as:

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

where dp[i][j] denotes the number of ways to reach cell (i, j).

inputFormat

The first line of input contains two integers m and n which denote the number of rows and columns of the grid respectively. Following this, there are m lines each containing n space-separated integers representing the grid cells. A value of 0 indicates an open cell and 1 indicates an obstacle.

outputFormat

The output is a single integer that represents the number of unique paths from the top-left corner to the bottom-right corner of the grid, avoiding obstacles.

3 3
0 0 0
0 1 0
0 0 0

2