Unique Paths with Obstacles

You are given an \(m \times n\) grid where each cell is either free or blocked. A free cell is represented by 0 and a blocked cell by 1. A robot is initially located at the top-left corner (cell (0, 0)) and needs to reach the bottom-right corner (cell (m-1, n-1)). The robot can only move either right or down at any point in time.

Your task is to calculate the number of distinct paths the robot can take to reach the destination without stepping on any obstacles.

Note: If the starting or ending cell is blocked, then there is no valid path. The transition relation for dynamic programming can be expressed as:

\(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}\)

inputFormat

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

m n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
... 
rowm_element1 rowm_element2 ... rowm_elementn

Here, m is the number of rows and n is the number of columns in the grid. Each of the following m lines contains n integers (either 0 or 1), where 0 indicates a free cell and 1 indicates an obstacle.

outputFormat

The output should be a single integer printed to standard output (stdout) representing the number of distinct 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