Cherry Pickup

I had this on a Two Sigma quant onsite and the trick that finally made it click was the equivalence: "a single walk THERE and BACK" is exactly the same as "two simultaneous walks both going from top-left to bottom-right, both moving DOWN or RIGHT". With the round-trip flattened into two parallel forwards walks, the state collapses from (r1, c1, dir, r2, c2, dir) to (r1, c1, r2, c2), and the manhattan-distance constraint cuts that to (r1, c1, r2) since c2 = r1 + c1 - r2. The catalog covered unique-paths and minimum-path-sum, but it skipped this two-walk variant.

Cherry Pickup

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers:

• 0 means the cell is empty, so you can pass through.
• 1 means the cell contains a cherry; you can pass through and pick the cherry, replacing the cell with 0.
• -1 means the cell contains a thorn that blocks your path.

Return the maximum number of cherries you can collect by following the rules below:

• Starting at the top-left position (0, 0), reach the bottom-right (n - 1, n - 1) by moving RIGHT or DOWN.
• After reaching (n - 1, n - 1), return to (0, 0) by moving LEFT or UP.
• When passing through a path cell containing a cherry, pick it up; the cell becomes empty.
• If there is no valid path between (0, 0) and (n - 1, n - 1), return 0.

Examples

Example 1:

• Input: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]
• Output: 5
• Explanation: Walk down the left column to (2, 0) (collecting 1 + 1 = 2), right to (2, 2) (collecting 1 + 1 = 2), then return up the diagonal collecting the remaining 1 at (0, 1). Total: 5.

Example 2:

• Input: grid = [[1, 1, -1], [1, -1, 1], [-1, 1, 1]]
• Output: 0
• Explanation: Every path from corner to corner is blocked by a thorn.

Example 3:

• Input: grid = [[1]]
• Output: 1
• Explanation: One cherry at the only cell.

Example 4:

• Input: grid = [[1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1]]
• Output: 15
• Explanation: A spine of cherries down the middle column gives 15 total.

Constraints

• n == grid.length == grid[i].length.
• 1 <= n <= 50.
• grid[i][j] is -1, 0, or 1.
• grid[0][0] != -1.
• grid[n - 1][n - 1] != -1.

Follow-up

Why is the round-trip equivalent to two simultaneous forwards walks? A round trip from (0, 0) to (n - 1, n - 1) and back is one walk from (0, 0) to (n - 1, n - 1) followed by another walk reversed. By symmetry, reversing the second walk gives a SECOND walk from (0, 0) to (n - 1, n - 1). Maximizing total cherries over both walks (with overlap counted once) is the same as picking up the same cherries on the round trip. The synchronization invariant is that both walks have the same step count, so r1 + c1 == r2 + c2 at every step.