Unique Paths in a Grid with Obstacles

You are given an m x n grid representing a game board. Each cell in the grid is either free (denoted by 0) or contains an obstacle (denoted by 1). Your task is to compute the number of unique paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (m-1,n-1)) by only moving right or down at any step.

If the starting cell or the ending cell is an obstacle, no valid path exists.

The problem can be solved using dynamic programming. The recurrence relation is given by:

$$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}$$

with the base condition $$dp_{0,0} = 1$$ (if there is no obstacle at the start).

inputFormat

The input is provided via standard input (stdin). The first line contains two integers m and n representing the number of rows and columns of the grid, respectively. This is followed by m lines, each containing n integers (0 or 1) separated by spaces, representing the grid.

outputFormat

The output is a single integer on standard output (stdout) which represents the number of unique paths from the top-left corner to the bottom-right corner.

3 3
0 0 0
0 0 0
0 0 0

6