Unique Paths With Obstacles

You are given a grid of size \( n \times m \) consisting of integers 0 and 1. A cell with 0 represents an open space, while a cell with 1 represents an obstacle. Your task is to find the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)), moving only to the right or down at each step.

If either the starting cell or the destination cell contains an obstacle, the answer is 0. The recurrence relation used to compute the number of paths for a free cell \( (i,j) \) is given by:

[ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]

when \( grid[i][j] = 0 \). If \( grid[i][j] = 1 \), then \( dp[i][j] = 0 \).

inputFormat

The first line contains two integers, ( n ) and ( m ), representing the number of rows and columns, respectively. This is followed by ( n ) lines, each containing ( m ) space-separated integers (0 or 1) that represent the grid.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2