Unique Paths with Obstacles

This problem is a variation of the classic grid-based dynamic programming challenge. Given a two-dimensional grid where some cells are marked as obstacles, you are tasked with calculating the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time. An obstacle is denoted by a 1 and an empty cell by a 0.

The solution involves using a dynamic programming approach where you construct a 2D array \(dp\) such that \(dp[i][j]\) represents the number of ways to reach cell \((i, j)\) without stepping on an obstacle. The recurrence relation is given by:

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

The starting cell at the top-left corner should be initialized to 1 if there is no obstacle. If the starting point itself is blocked, the answer is 0.

inputFormat

The input is given from standard input and follows this format:

• The first line contains an integer (T), the number of test cases.
• For each test case:
  • The first line contains two space-separated integers (m) and (n), the dimensions of the grid.
  • The next (m) lines each contain (n) space-separated integers representing the grid cells, where 0 denotes an empty cell and 1 denotes an obstacle.

outputFormat

For each test case, output a single integer on a new line representing the number of unique paths from the top-left corner to the bottom-right corner that avoid obstacles.## sample

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

2
1
0
6