Unique Paths with Obstacles

Given an m × n grid where each cell is either free (denoted by 0) or an obstacle (denoted by 1), compute the number of unique paths from the upper-left corner to the lower-right corner. You are only allowed to move either right or down at any point in time.

If the starting cell or the ending cell is an obstacle, then the answer is 0. The recurrence relation used to compute the number of paths is given by the formula:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) when the cell \((i, j)\) is free.

This problem requires handling boundary conditions and obstacles correctly, ensuring that paths blocked by obstacles are not counted.

inputFormat

The first line of input contains two integers m and n representing the dimensions of the grid.

The next m lines each contain n space-separated integers (0 or 1) representing the grid. A 0 indicates a free cell and a 1 indicates an obstacle.

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner, considering obstacles.

3 3
0 0 0
0 1 0
0 0 0

2