Show problems as
Classic problem #741HardArrayDynamic ProgrammingMatrix

Cherry Pickup

Real-world version: Round Trip Parcel Pickup
Tracked in this browser only
Read Cherry Pickup on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstProbability & Expectations · Dynamic Programming, animated step by step

A mail room floor is laid out as an n x n grid of tiles. grid[r][c] is 1 when a parcel sits on that tile, 0 when the tile is clear, and -1 when a pillar stands on the tile so nothing can enter it.

A trolley starts on the top-left tile and rolls to the bottom-right tile, every move taking it one tile right or one tile down. From there it rolls back to the top-left tile, every move taking it one tile left or one tile up. Each time the trolley enters a tile that still holds a parcel it loads that parcel and the tile becomes clear, so a tile pays out at most once across the whole trip. The tile it starts on counts as visited, so a parcel resting there is loaded before the trolley sets off, and a one-tile floor still pays out whatever sits on it.

Report the largest number of parcels the trolley can be carrying once it is back on the top-left tile. If the pillars leave no way to roll from the top-left tile to the bottom-right tile, the trip cannot be made and the answer is 0.

Examples

Example 1

Input
grid = [[0, 1, 1], [1, 1, 0], [0, 1, 0]]
Output
5

Going out along the top row and down the last column loads the parcels at (0,1) and (0,2). Coming back down the first column and across the middle row loads (1,0), (1,1) and (2,1), which is every parcel on the floor.

Example 2

Input
grid = [[1, 1], [-1, 1]]
Output
3

The pillar at (1,0) leaves only one route each way, so the trolley collects the three parcels on it and the return trip finds those tiles already clear.

Example 3

Input
grid = [[1, -1], [-1, 1]]
Output
0

Both tiles next to the start are pillars, so the bottom-right tile can never be reached and no trip happens.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def round_trip_parcels(grid: list[list[int]]) -> int:
Java
public int roundTripParcels(int[][] grid)

More on the same topics