hard +40 pts

Cherry Pickup Maximum

Collect maximum cherries with two paths from top-left to bottom-right on a grid with obstacles.

You are given an n x n grid where each cell contains an integer. A positive integer represents the number of cherries in that cell, 0 means an empty cell, and -1 means a blocked cell that cannot be entered. You start at the top-left corner (0,0) and must reach the bottom-right corner (n-1,n-1). You can move only right or down, and you cannot step onto a cell with -1. On your way, you collect all cherries in each cell you visit. After reaching the bottom-right corner, you must return to the top-left corner by moving only left or up. You may visit a cell only once per path, and if you visit a cell on both the forward and return trip, you collect its cherries only once. (Note: the forward and return paths together can be thought of as two people walking from top-left to bottom-right simultaneously.) Write a function `cherry_pickup(grid: List[List[int]]) -> int` that returns the maximum number of cherries you can collect. If there is no valid path from top-left to bottom-right, return 0. The input grid is a square matrix of size n x n where 1 <= n <= 50. Each cell contains integers in the range [-1, 100].

Constraints

n is between 1 and 50. grid[i][j] is between -1 and 100. The function must handle n up to 50 efficiently (O(n^3) time is acceptable).

Example

>>> cherry_pickup([[0,1,-1],[1,0,-1],[1,1,1]])
5
>>> cherry_pickup([[1]])
1
>>> cherry_pickup([[0,0],[0,0]])
0
>>> cherry_pickup([[0,1,0],[1,1,1],[0,1,0]])
6
40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of two simultaneous walkers starting at (0,0) and moving to (n-1,n-1) with right/down moves.
Use DP state (r1, c1, r2) where c2 = r1 + c1 - r2.
If either walker steps on a -1, that path is invalid; return -infinity.
Handle overlapping cells by counting cherries only once.
The answer is max(0, dp[n-1][n-1][n-1]) because you might not reach the end.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.