Counting Distinct Paths in a Grid with Obstacles

You are given a grid of size (m \times n) composed of cells. Each cell is either empty (denoted by 0) or contains an obstacle (denoted by 1). Your task is to determine the number of distinct paths from the top-left cell (starting point) to the bottom-right cell (destination) under the condition that you can only move either down or right at any step and you cannot step into a cell that contains an obstacle.

The problem can be formulated using dynamic programming. Let (dp[i][j]) denote the number of distinct paths to reach cell ((i,j)) from the start. 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} ] with the initialization (dp[0][0] = 1) (provided the starting cell is not blocked), and any cell that is blocked (i.e. grid value equals 1) has 0 paths. If the start or destination cell is blocked, the answer is 0.

Read the grid from the standard input and print the number of distinct paths to the standard output.

inputFormat

The first line contains two integers (m) and (n) representing the number of rows and columns of the grid, respectively. The following (m) lines each contain (n) integers (either 0 or 1), separated by spaces, where 0 represents an empty cell and 1 represents an obstacle.

outputFormat

Output a single integer which is the number of distinct paths from the top-left corner to the bottom-right corner of the grid. If no valid path exists, output 0.## sample

3 3
0 0 0
0 1 0
0 0 0

2