Unique Paths in a Grid with Obstacles

In this problem, you are given a grid consisting of 0s and 1s, where 0 represents a free cell and 1 represents an obstacle. Your task is to determine the number of unique paths from the top-left corner (starting point) to the bottom-right corner (destination) of the grid, moving only right or down. If either the starting cell or the destination cell is blocked, the answer is 0.

The approach typically involves dynamic programming. Define a DP table (dp) such that (dp[i][j]) is the number of ways to reach cell ((i, j)). The recurrence relation is given by:

[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1 \ \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{otherwise} \end{cases} ]

with the proper handling of boundaries. This problem is a classic example of applying dynamic programming techniques to a grid-based challenge.

inputFormat

The input begins with an integer (T) representing the number of test cases. Each test case starts with two integers, (R) and (C), representing the number of rows and columns in the grid. This is followed by (R) lines, each containing (C) integers (either 0 or 1), where 0 indicates an empty cell and 1 indicates an obstacle.

Example:

2 3 3 0 0 0 0 1 0 0 0 0 2 2 0 1 1 0

outputFormat

For each test case, print a single integer representing the number of unique paths from the top-left to the bottom-right of the grid. Each result should be printed on a new line.## sample

2
3 3
0 0 0
0 1 0
0 0 0
2 2
0 1
1 0

2
0