Cherry Pickup

Hard

You are given an n x n grid where each cell is 0 (empty), 1 (a cherry), or -1 (a thorn you cannot pass).

Walk from (0, 0) to (n-1, n-1) moving only right or down, then walk back from (n-1, n-1) to (0, 0) moving only left or up. You pick up every cherry you step on, and that cell becomes empty.

Return the maximum number of cherries you can collect. If there is no valid round trip, return 0.

Example 1

Input:  grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: Go down the left column and along the bottom row collecting 4 cherries, then return through the middle collecting 1 more.

Example 2

Input:  grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Explanation: The thorns block every round trip.

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