Unique Paths with Obstacles

You are given an m x n grid called obstacleGrid where each cell in the grid is either 0 or 1. Here, 0 represents an empty cell and 1 represents an obstacle. Your task is to determine the number of unique paths from the top-left corner (start) to the bottom-right corner (destination) of the grid. You can only move either down or right at any step.

If the starting cell or the destination cell contains an obstacle, then it is impossible to traverse the grid, and the number of unique paths is 0.

You may solve this problem using dynamic programming. The recurrence relation for calculating the number of ways to reach cell \( (i,j) \) is given by:

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

with the initial condition \( DP[0][0] = 1 \) provided there is no obstacle at the start.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains two integers m and n separated by a space, where m is the number of rows and n is the number of columns.
• The next m lines each contain n integers separated by spaces. Each integer is either 0 (representing an empty cell) or 1 (representing an obstacle).

outputFormat

Output a single integer via standard output (stdout) 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