Counting Paths in a Grid with Obstacles

Given a grid of size \(R \times C\), each cell is either accessible (represented by 0) or blocked (represented by -1). Your task is to compute the number of distinct paths from the top-left cell (cell (1,1)) to the bottom-right cell (cell \( (R,C)\)). You can only move either right or down.

The dynamic programming recurrence for an accessible cell \((i,j)\) is:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

with the base condition \( dp[1][1] = 1 \) (if the start cell is not blocked) and if a cell is blocked, it has 0 ways.

Constraints: \(1 \le R, C \le 100\).

inputFormat

The input is read from stdin as follows:

The first line contains two integers (R) and (C), representing the number of rows and columns of the grid.

The following (R) lines each contain (C) integers separated by spaces. A value of 0 indicates an accessible cell, and -1 indicates a blocked cell.

outputFormat

Output a single integer to stdout denoting the number of distinct paths from the top-left cell to the bottom-right cell.## sample

3 3
0 0 0
0 -1 0
0 0 0

2