Unique Paths in a Grid with Obstacles

Given a grid of size \(n \times m\), your task is to calculate the number of unique paths from the top-left corner \((1,1)\) to the bottom-right corner \((n,m)\). You can only move either right or down at any step. The grid contains obstacles specified by their 1-indexed coordinates; you cannot step on these cells. If the starting cell or the ending cell is blocked by an obstacle, the answer is \(0\).

Use dynamic programming to solve this problem by constructing a table \(dp\) where \(dp[i][j]\) denotes the number of ways to reach the cell \((i,j)\) from the start. The recurrence relation is given by:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) if cell \((i,j)\) is not an obstacle, with the base condition \(dp[1][1] = 1\) (provided that cell is not an obstacle).

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains three integers \(n\), \(m\), and \(k\) representing the number of rows, columns, and obstacles, respectively. This is followed by \(k\) lines, each containing two integers \(x\) and \(y\) denoting the 1-indexed position of 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 to the bottom-right corner of the grid.

1
3 3 0

6