Unique Paths with Obstacles

You are given an m × n grid. Each cell in the grid is either empty or contains an obstacle. The grid is represented by a matrix where a cell with a value of 0 indicates an empty cell and a cell with a value of 1 indicates an obstacle.

You start at the top-left corner (cell (1, 1)) and your goal is to reach the bottom-right corner (cell (m, n)). You can only move either down or right at any point in time.

Determine the number of unique paths from the top-left corner to the bottom-right corner. If the starting or ending cell is an obstacle, then there is no valid path. The transition relation for the dynamic programming solution is given by:

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

Note: The indices follow 0-indexing in implementation but are described above using 1-indexing for clarity.

inputFormat

The input is given via standard input and has the following format:

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

outputFormat

Output a single integer to the standard output which denotes the number of unique paths from the top-left corner to the bottom-right corner of the grid.

3 3
0 0 0
0 1 0
0 0 0

2