#741
Cherry Pickup
master · 1725 · lc hard +32 · verified · 39.1% accepted · 4,646 likes · top 18%
Description
You are given an n x n grid where each cell is 0 (empty), 1 (a cherry), or -1 (a thorn). Starting at (0, 0), travel to (n-1, n-1) moving only right or down, collecting cherries along the way (each cherry can only be picked once). Then return to (0, 0) moving only left or up, collecting any remaining cherries. Thorns block movement.
Return the maximum cherries collectible on both trips combined, or 0 if no valid path exists.
Example 1:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.
Example 2:
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Code
1
2
3