Taco: Count Distinct Paths in a Garden

You are given a grid representing a garden. Each cell is either walkable (0) or blocked by a plant (1). Starting at the top-left corner, your task is to count all distinct paths to the bottom-right cell. Movement is restricted to only right or downward steps. A valid path should avoid cells containing plants.

The number of ways to reach a cell can be computed using dynamic programming. In particular, if we let \(dp[i][j]\) denote the number of ways to reach cell \((i, j)\), then for each walkable cell the transition is given by:

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

with the base condition \(dp[0][0] = 1\) if the starting cell is walkable. Compute the number of distinct paths using this approach.

inputFormat

The input is provided via stdin and has the following format:

• The first line contains two integers, R and C, representing the number of rows and columns in the grid.
• The next R lines each contain C space-separated integers (either 0 or 1), representing the grid configuration.

outputFormat

Output a single integer to stdout which is the number of distinct paths from the top-left cell to the bottom-right cell.

3 3
0 0 0
0 1 0
0 0 0

2