Unique Paths in a Grid with Obstacles

You are given an m x n grid representing a map, where each cell contains either 0 (empty) or 1 (obstacle). A robot starts at the top-left corner and aims to reach the bottom-right corner. The robot can only move either down or right at any point in time. Your task is to calculate the number of unique paths from the top-left to the bottom-right corner without stepping on any obstacles.

The dynamic programming formulation for this problem is given by the recurrence formula:

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

Make sure to take into account some edge cases such as when the starting cell or the ending cell is blocked, and when the grid is just a single cell.

inputFormat

The input consists of:

• The first line contains two integers m and n representing the number of rows and columns in the grid.
• The next m lines contain n integers each (either 0 or 1) separated by spaces, representing the grid.

Note: Input is read from standard input (stdin).

outputFormat

Output a single integer, which is the number of unique paths from the top-left to the bottom-right corner. Output is written to standard output (stdout).

3 3
0 0 0
0 1 0
0 0 0

2