Cherry Pickup

You are given an 'n' x 'n' grid where each cell contains one of three values:

0: An empty cell you can pass through.

1: A cell with a cherry you can pick up. After you pick it, the cell becomes empty (0).

-1: A thorn that blocks your path.

Your task is to find the maximum number of cherries you can collect by completing a round trip, following these rules:

1) Forward Trip: Start at (0, 0) and travel to (n-1, n-1) by moving only right or down.

2) Return Trip: From (n-1, n-1), travel back to (0, 0) by moving only left or up.

3) You can only move through cells that are not thorns (-1).

4) If there is no valid path for either the forward or return trip, you can collect 0 cherries.

Input Format:

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

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

Output Format:

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

Note:

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.