Unique Paths in a Maze

You are given a maze represented as a grid with . (free cell) and # (obstacle). Your task is to compute the number of unique paths from the top-left cell to the bottom-right cell, moving only right or down. If either the start or the finish is blocked, the answer is 0. The problem can be solved with a dynamic programming approach by using the recurrence:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\), with the base case \(dp[0][0] = 1\) (if not an obstacle) and \(dp[i][j] = 0\) if cell \( (i,j) \) is blocked.

For multiple test cases, you should process each maze separately and output the answer for each maze in a new line.

inputFormat

The input is read from standard input. The first line contains an integer T (number of test cases). For each test case:

• The first line contains two integers N and M representing the number of rows and columns of the maze.
• This is followed by N lines, each containing a string of M characters (each character is either . or #).

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 cell.

1
3 3
...
.#.
...

2