Unique Paths with Obstacles

You are given an M (\times) N grid represented by a matrix where each cell is either empty (0) or blocked by an obstacle (1). Your task is to determine the number of unique paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (M-1, N-1)). At any point, you may only move either right or down. If the start or the destination cell is an obstacle, the result should be 0.

The problem can be modeled with dynamic programming. Let (dp[i][j]) denote the number of ways to reach cell ((i, j)). The recurrence relation is given by:

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

The initial condition is (dp[0][0] = 1) if (matrix[0][0]=0), otherwise 0. Compute (dp[M-1][N-1]) to get the final answer.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) that denotes the number of test cases. For each test case, the first line contains two integers (M) and (N) which represent the dimensions of the matrix. This is followed by (M) lines, each containing (N) space-separated integers (either 0 or 1) representing the grid.

outputFormat

For each test case, output a single integer on a new line, which is the number of unique paths from the top-left corner to the bottom-right corner, avoiding obstacles. The output is written to standard output (stdout).## sample

1
3 3
0 0 0
0 1 0
0 0 0

2