Unique Paths in a Grid with Obstacles

You are given a 2D grid representing a maze where each cell is either free (0) or contains an obstacle (1). Starting from the top-left corner, you need to determine the number of unique paths to reach the bottom-right corner. Movement is only allowed to the right or down. If the starting cell or destination cell contains an obstacle, then there is no valid path.

The grid is provided as multiple test datasets. Each dataset begins with two integers \(h\) and \(w\) (representing the number of rows and columns, respectively), followed by \(h\) lines of \(w\) integers each. A dataset with \(h = 0\) and \(w = 0\) marks the end of input.

Your task is to implement a function that computes the number of unique paths for each dataset using dynamic programming. The recurrence relation for the number of ways is given by:

[ \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 initialization \(\text{dp}[0][0] = 1\) if \(grid[0][0] = 0\), else 0.

inputFormat

The input is read from the standard input (stdin) and consists of multiple test datasets. Each dataset is structured as follows:

• The first line contains two integers \(h\) and \(w\) separated by a space, where \(h\) and \(w\) denote the number of rows and columns of the grid.
• The next \(h\) lines each contain \(w\) integers (0 or 1) separated by spaces, representing the grid.
• Datasets are separated by a blank line. The input terminates with a dataset where \(h = 0\) and \(w = 0\); this dataset should not be processed.

outputFormat

For each dataset, output a single integer on a new line indicating the number of unique paths from the top-left cell to the bottom-right cell.

The output is printed to the standard output (stdout).

## sample

3 3
0 0 0
0 1 0
0 0 0

0 0

2

</p>