Apple Pickup Problem Statement

Alice has a garden represented as a ‘N’ * ‘N’ grid called ‘MATRIX’. She wants to collect apples following these rules:

• 1 -> Alice can pick an apple from this cell and pass through.
• -1 -> This cell contains a bush that Alice cannot visit.
• 0 -> This cell is empty, and Alice can pass through.

Alice starts from the top-left corner (0,0) and must reach the bottom-right corner (‘N’-1,’N’-1) and return back to (0,0). Her goal is to collect the maximum number of apples during this round trip.

She can move:

• Right or Down towards the bottom-right corner.
• Left or Up towards the top-left corner.

If there's no valid path from (0,0) to (‘N’-1, ‘N’-1), Alice collects no apples.

Example:

Input:

matrix = [
[1, 1, -1, 1],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, -1, -1, 1]
]

Output:

9

Explanation:

A possible path:

Towards bottom-right: (0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3) collecting 6 apples.

Returning to top-left: (3,3) -> (2,3) -> (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0) collecting 3 apples.

Total apples collected = 9.

Input Format:

The first line contains an integer ‘T’ representing the number of test cases.
Each test case begins with an integer ‘N’, the size of the grid.
Each of the following ‘N’ lines contains ‘N’ space-separated integers representing the grid.

Output Format:

Print a single integer per test case representing the maximum number of apples Alice can collect.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 50
• -1 ≤ MATRIX[i][j] ≤ 1
• Time limit: 1 second

Note:

You don’t have to print anything; just implement and return the answer.