Maximum Path Sum in a Grid with Obstacles

Problem Statement

You are given an n x n grid filled with integers and obstacles. Your goal is to find a path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1) that maximizes the sum of the integers along the path. You can only move to the right or down at each step. Obstacles are represented by the character ‘x’, and you cannot move through these cells. If there is no path from the top-left corner to the bottom-right corner, the maximum sum is considered to be 0.

Input Format

• The first line contains a single integer t, the number of test cases.
• For each test case:
• The first line contains a single integer n, representing the size of the grid.
• This is followed by n lines, each containing n characters (without spaces). Each character is either a digit (0-9) representing the integer value of the cell, or ‘x’ representing an obstacle.

Output Format

For each test case, output a single line containing two integers:

• The first integer is the maximum sum that can be obtained by any path from the top-left corner to the bottom-right corner.
• The second integer is the number of distinct paths that yield this maximum sum. If no such path exists, output 0 0.

Constraints

• (1 <= t <= 100)
• (1 <= n <= 100)

Sample Input and Output

Sample Input #1:

1
3
1 3 1
1 x 1
1 1 2

Sample Output #1:

8 1

Explanation #1:

In this grid, there is exactly one path that provides the maximum sum: 1 -> 3 -> 1 -> 1 -> 2, yielding a sum of 8. The path moves right, right, down, down, capturing the maximum value possible under the movement constraints.

Sample Input #2:

1
4
1 2 3 4
x x 2 1
1 2 x 2
1 1 1 1

Sample Output #2:

12 1

Explanation #2:

The optimal path for this grid is 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> 1, with a total sum of 12. There’s only one path that achieves this sum due to the positioning of obstacles. This path involves moving right to the end of the first row, then down and right when possible, navigating around obstacles.

Sample Input #3

2
3
123
x5x
xx8
4
1x2x
xxxx
2xxx
xxx3

Sample Output

0 0
0 0

Explanation

• For the first test case, there are no paths from (0,0) to (2,2) because of obstacles, so the output is 0 0.
• For the second test case, there are no paths from (0,0) to (3,3) because of obstacles blocking all possible routes, so the output is 0 0.