Unique Path Counting in a Grid with Obstacles

You are given an ( n \times m ) grid where each cell contains either a 0 or a 1. A cell with a 1 represents an obstacle, and a cell with a 0 represents a free space. You need to determine the number of distinct paths from the top-left corner to the bottom-right corner of the grid. From any cell, you are only allowed to move either right or down. If the starting cell or the ending cell is blocked (i.e. contains a 1), then the answer is 0.

The recurrence relation used in the solution is given by:\ ( dp[i][j] = dp[i-1][j] + dp[i][j-1] ) for cells ( (i, j) ) that are not obstacles. The starting cell ( dp[0][0] ) is initialized to 1 if it is not an obstacle.

inputFormat

The first line contains two integers ( n ) and ( m ) representing the number of rows and columns of the grid. The next ( n ) lines each contain ( m ) space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner.## sample

3 3
0 0 0
0 0 0
0 0 0

6