Unique Paths in a Grid

In this problem, you are given a grid of size (R \times C) represented by a string. The grid contains characters '0' and '1', where '0' represents a free cell and '1' represents an obstacle. Your goal is to determine the number of unique paths from the top-left corner (start) to the bottom-right corner (destination) of the grid if you are only allowed to move either right or down at any point in time.

A dynamic programming approach is typically used to solve this problem. You can define (dp[i][j]) as the number of ways to reach cell ((i, j)). 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{otherwise.} \end{cases})

If the starting or ending cell is blocked, the answer is 0. Please note that the grid is provided as input in a specific format (see Input Description) and the output should be printed as a single integer representing the number of unique paths.

inputFormat

The input is given through standard input (stdin) and consists of multiple lines. The first line contains two integers (R) and (C) separated by a space, representing the number of rows and columns respectively. This is followed by (R) lines, each containing a string of length (C) consisting of characters '0' (free cell) and '1' (obstacle).

outputFormat

Print a single integer to standard output (stdout) representing the number of unique paths from the top-left corner to the bottom-right corner of the grid.## sample

3 3
000
010
000

2