Unique Paths in a Grid with Obstacles

Given an $m \times n$ grid, where some cells are blocked (represented by 1) and others are free (represented by 0), determine the number of unique paths from the top-left corner to the bottom-right corner. You can only move either right or down at any step. A cell that is blocked cannot be traversed. The answer must be computed using dynamic programming or any efficient method.

inputFormat

The first line of input contains two integers m and n — the number of rows and columns, respectively. This is followed by m lines, each containing n space-separated integers (0 or 1), representing the grid where 0 indicates a free cell and 1 indicates a blocked cell.

outputFormat

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

3 3
0 0 0
0 1 0
0 0 0

2