Cherry Pickup

The first line of input contains an integer 'n'.

The next 'n' lines each contain 'n' space-separated integers, representing the grid.

Print a single integer representing the maximum number of cherries you can collect.

A key insight is that the problem of a "forward trip" and a "return trip" is equivalent to finding two independent forward trips from (0, 0) to (n-1, n-1). The total cherries collected is the sum of cherries on both paths, taking care not to double-count cherries at cells visited by both paths.

This "two-person" traversal can be solved with dynamic programming. The state of the DP needs to track the positions of both "people" simultaneously. A state dp[r1][c1][r2] can represent the max cherries collected when person 1 is at (r1, c1) and person 2 is at (r2, c2), where c2 = r1 + c1 - r2.

Sample Input 1:

3
0 1 -1
1 0 -1
1 1 1

Sample Output 1:

5

Explanation for Sample 1:

An optimal path for the first trip (or "person 1") is `down -> down -> right -> right`, visiting `(0,0), (1,0), (2,0), (2,1), (2,2)`. This collects 4 cherries. The grid becomes:
`0 1 -1`
`0 0 -1`
`0 0 0`
An optimal path for the return trip (or "person 2") on this modified grid is `left -> up -> up -> left`, visiting `(2,2), (2,1), (1,1), (0,1), (0,0)`. This collects 1 more cherry from `(0,1)`.
Total cherries collected = 5.

Sample Input 2:

3
1 1 -1
1 -1 1
-1 1 1

Sample Output 2:

0

Explanation for Sample 2:

There is no valid path from `(0, 0)` to `(2, 2)` that avoids the thorns. Therefore, no cherries can be collected.

Expected Time Complexity:

The expected time complexity is O(N^3).

Constraints:

1 <= n <= 50
grid[i][j] is -1, 0, or 1.
grid[0][0] and grid[n-1][n-1] will not be -1.

Time limit: 1 sec