Distinct Paths in a Grid with Obstacles

You are given a grid of size R x C, where each cell is either 0 (open) or 1 (an obstacle). Your task is to compute the total number of distinct paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (R-1, C-1)). You can only move either right or down at any step.

If either the starting cell or the destination cell is blocked, then the output should be 0. Otherwise, you can use dynamic programming with the following recurrence relation to compute the number of paths:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) for each open cell (i, j).

Note that if a cell is blocked, then no path can go through it, and its dp value remains 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers R and C, the number of rows and columns respectively.
• The next R lines each contain C integers (0 or 1) representing the grid. 0 denotes an open cell, while 1 denotes an obstacle.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2