Unique Paths in a Grid with Obstacles

You are given an m x n grid where each cell is either open (0) or blocked (1). Your task is to calculate the number of unique paths from the top-left cell to the bottom-right cell, moving only right or down, while avoiding blocked cells.

If either the starting or the ending cell is blocked, there are no valid paths. Otherwise, let \(dp(i, j)\) denote the number of ways to reach cell \((i,j)\). The recurrence relation is:

\(dp(i, j) = dp(i-1, j) + dp(i, j-1)\)

with the initial condition \(dp(0,0)=1\) and \(dp(i,j)=0\) if the cell \((i, j)\) is blocked.

inputFormat

The first line contains two integers m and n, representing the number of rows and columns in the grid.

Each of the next m lines contains n space-separated integers (either 0 or 1) representing the grid cells.

outputFormat

Output a single integer representing 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