Unique Paths with Obstacles

You are given a grid of size m x n where each cell is either 0 (empty) or 1 (blocked). A robot is initially located at the top-left cell (i.e., first row, first column) and needs to reach the bottom-right cell. The robot can only move either down or right at any point in time.

Your task is to compute the number of unique paths from the top-left corner to the bottom-right corner such that the robot does not go through a blocked cell.

Note: If the starting or the ending cell is blocked, the answer is 0.

The dynamic programming recurrence used is defined as follows:

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

inputFormat

The first line contains two integers m and n which represent the number of rows and columns respectively in the grid.

The next m lines each contain n integers (each either 0 or 1), representing the grid.

outputFormat

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

## sample

3 3
0 0 0
0 1 0
0 0 0

2