Count Valid Paths in a Grid with Obstacles

You are given an m x n grid represented by a matrix, where 0 represents a free cell and 1 represents an obstacle. You can only move either right or down at any point in time. Your task is to count the number of distinct valid paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (m-1,n-1)). A valid path cannot pass through any obstacles. If the starting cell or the destination cell is blocked, then the answer is 0.

The solution should be implemented to read input from stdin and write the output to stdout. All formulas in the description must be formatted in LaTeX. For example, the number of paths can be described as solving the recurrence relation:

$$ dp[i][j] = \begin{cases}\ 0,&\text{if } grid[i][j]=1 \\ dp[i-1][j] + dp[i][j-1],&\text{otherwise} \end{cases}$$

inputFormat

The input is provided via stdin in the following format:

m n
row1_element1 row1_element2 ... row1_element_n
row2_element1 row2_element2 ... row2_element_n
...
rowm_element1 rowm_element2 ... rowm_element_n

Here, m and n denote the number of rows and columns of the grid respectively. Each grid element is either 0 (a free cell) or 1 (an obstacle).

outputFormat

Output a single integer to stdout representing the number of distinct valid 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