223. Cherry Pickup
Hard•
A square grid contains 0 for an empty cell, 1 for a cherry, and -1 for a blocked cell. Travel from the top-left to the bottom-right using only right or down moves, then return using only left or up moves. Blocked cells cannot be visited.
A cherry can be collected only once across the entire round trip. Return the maximum cherries you can collect, or 0 if no complete route exists. Do not modify grid.
Example 1:
Outward route
Return route after collection
Input: grid = [[1,0,1],[0,-1,0],[1,0,1]]
Output: 4
Explanation: The central thorn separates two boundary routes. Going down, down, right, right collects the start, bottom-left, and destination cherries: 3. Returning up, up, left, left collects only the remaining top-right cherry: 1. The shared endpoints count once, giving 4 total.
Example 2:
Input: grid = [[0,-1],[-1,0]]
Output: 0
Explanation: Both possible first moves land on thorns. There is no outward path to the destination, so no round trip can collect cherries and the result is 0.
Example 3:
Input: grid = [[1,0],[0,1]]
Output: 2
Explanation: Only the start and destination contain cherries. Both legs may visit both endpoints, but each cherry is collected once, giving 2 rather than 4.
Constraints
- 1 <= grid.length == grid[row].length <= 50
- Every cell is -1, 0 or 1.
- The start and destination are not blocked.
Accepted4/6|Acceptance Rate66.7%