Unique Paths with Obstacles

You are given a grid with m rows and n columns. Each cell in the grid is either free (represented by 0) or blocked with an obstacle (represented by 1).

A robot starts at the top-left cell (cell (1,1)) and needs to travel to the bottom-right cell (cell (m,n)). The robot can only move either right or down at any point in time.

Your task is to compute the number of unique paths from the start to the destination, avoiding obstacles.

If either the starting cell or the destination cell is an obstacle, then the answer is 0.

The transition can be described with the following dynamic programming formula in \(\LaTeX\):

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

The answer is given by \(dp[m-1][n-1]\).

inputFormat

The first line of input contains two integers \(m\) and \(n\), representing the number of rows and columns, respectively.

This is followed by \(m\) lines, each containing \(n\) space-separated integers. Each integer is either 0 (free cell) or 1 (obstacle).

outputFormat

Output a single integer 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 1 0
0 0 0

2