Unique Paths in a Grid with Obstacles

This problem asks you to calculate the number of unique paths an adventurer can take to travel from the top-left corner to the bottom-right corner of a grid while avoiding obstacles. The grid consists of m rows and n columns, where each cell is either passable (represented by '0') or blocked by an obstacle (represented by '1'). The adventurer can only move down or right at any step.

The number of ways can be formally defined as:

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

Your task is to compute \( dp[m-1][n-1] \), considering that if either the starting cell or the ending cell is blocked, the output should be 0.

inputFormat

The input is given through standard input (stdin) and is formatted as follows:

• The first line contains two integers m and n, where m is the number of rows and n is the number of columns in the grid.
• The following m lines each contain a string of length n consisting of characters '0' and '1', representing the grid.

outputFormat

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

3 3
000
010
000

2