Distinct Paths in a Grid with Obstacles

You are given a grid with N rows and M columns. Each cell in the grid is either empty (represented by 0) or contains an obstacle (represented by 1). You need to find the number of distinct paths from the top-left corner to the bottom-right corner of the grid. At each step, you may only move either right or down. If the starting cell or the destination cell contains an obstacle, then no path exists.

Note: Use dynamic programming to solve this problem.

The number of ways is computed using the recurrence relation:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) if \(grid[i][j]=0\) and \(dp[i][j]=0\) if \(grid[i][j]=1\).

inputFormat

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

outputFormat

Output a single integer which is the number of distinct paths from the top-left corner to the bottom-right corner that avoid obstacles.

3 3
0 0 0
0 1 0
0 0 0

2