Unique Paths in a Grid with Obstacles

You are given a grid of size m x n consisting of characters '0' and '1'. A '0' denotes an empty space, while a '1' represents a boulder. A robot starts 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 compute the number of unique paths the robot can take to get to the destination while avoiding all boulders. If the starting cell or the destination cell is blocked, then the answer is 0.

The recurrence relation for dynamic programming can be written 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{otherwise} \end{cases} \]

with the initial condition \(\text{dp}[0][0]=1\) if the starting cell is not blocked.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains two integers m and n, representing the number of rows and columns of the grid respectively.
• The following m lines each contain n characters separated by spaces. Each character is either '0' (empty) or '1' (boulder).

outputFormat

Output to stdout a single integer, the number of unique paths from the top-left corner to the bottom-right corner.

3 3
0 0 0
0 1 0
0 0 0

2