Distinct Paths in a Grid with Obstacles

You are given a grid with dimensions \( n \times m \). Each cell in the grid is either empty (denoted by 0) or contains an obstacle (denoted by 1). A robot starts at the top-left cell, \( (0,0) \), and must reach the bottom-right cell, \( (n-1, m-1) \), by moving only down or right at each step.

Your task is to compute the number of distinct paths the robot can take to reach the destination. If either the starting cell or the destination cell is blocked by an obstacle, the answer is 0.

A dynamic programming approach can be used to solve this problem. Let \( dp[i][j] \) denote 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}$$

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the grid respectively.

The next \( n \) lines each contain \( m \) integers (each being either 0 or 1) separated by spaces, representing the grid cells.

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner, following the allowed moves.

3 3
0 0 0
0 0 0
0 0 0

6