Unique Paths with Obstacles

Given a grid represented as a 2D matrix of integers where \(0\) indicates an open cell and \(1\) indicates an obstacle, your task is to determine the number of unique paths from the top-left corner \((0, 0)\) to the bottom-right corner \((m-1, n-1)\). The traveler can only move either down or right at each step.

In an obstacle-free grid, the total number of unique paths is given by the formula \( \binom{m+n-2}{m-1} \). However, obstacles may block some paths, reducing this count significantly. Solve the problem by computing the number of valid paths while avoiding obstacles.

inputFormat

The first line of input contains two integers \(r\) and \(c\), representing the number of rows and columns in the grid respectively.

This is followed by \(r\) lines each containing \(c\) space-separated integers (either \(0\) or \(1\)) that describe the grid.

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner of the grid using only right and down moves.

3 3
0 0 0
0 0 0
0 0 0

6