Unique Paths in a Grid with Obstacles

Given an N x N grid where each cell is either open (0) or blocked (1), your task is to count the number of unique paths from the top-left corner to the bottom-right corner. You may only move right or down at any step, and you cannot traverse blocked cells.

If either the starting cell or the destination cell is blocked, the number of unique paths is 0. Otherwise, the number of unique paths can be computed using dynamic programming with the recurrence:

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

Here, dp[i][j] represents the number of ways to reach cell (i, j) in the grid.

inputFormat

The first line of input contains an integer T indicating the number of test cases. For each test case, the first line contains an integer N representing the size of the grid. This is followed by N lines, each containing N space-separated integers (0 or 1) which represent the grid.

outputFormat

For each test case, print a single integer on a new line, which is the number of unique paths from the top-left to the bottom-right cell of the grid.

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

2
1