Distinct Paths in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either a free cell represented by 0 or an obstacle represented by 1. Starting from the top-left corner, your task is to find the number of distinct paths to reach the bottom-right corner. You can only move either right or down at any step.

The problem can be solved using a dynamic programming approach. For every cell \( (i,j) \) that is not an obstacle, the recurrence is given by:

[ dp(i,j) = dp(i-1,j) + dp(i,j-1), ]

with the boundary condition \( dp(0,0)=1 \) if the starting cell is free. If either the start or the destination is blocked, the answer is 0.

inputFormat

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

outputFormat

Output a single integer, the number of distinct paths from the top-left corner to the bottom-right corner of the grid.

3 3
0 0 0
0 0 0
0 0 0

6