Unique Paths with Obstacles

Given an \(m \times n\) grid, where each cell is either empty (0) or contains an obstacle (1), determine the number of unique paths from the top-left corner to the bottom-right corner. The robot can only move either down or right. If the starting or ending cell contains an obstacle, then no path exists. You can use dynamic programming with the recurrence \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) (if the current cell is free) to solve the problem.

inputFormat

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

outputFormat

Print a single integer to standard output (stdout) representing 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