0200HardArrayDynamic ProgrammingMatrix

Round Trip Parcel Pickup

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def round_trip_parcels(grid: list[list[int]]) -> int:

Java

public int roundTripParcels(int[][] grid)

The intended approach

Time O(n^3)Space O(n^2)

Rolling back with left and up moves is the same shape of walk as rolling out with right and down moves, just read in reverse, so the round trip is equivalent to sending two trolleys out from the top-left tile at the same time and summing the tiles they cover between them. Advance both in lockstep: after k moves each one sits on the tile band where row plus column equals k, so a state is just the pair of rows and the column follows. A tile shared by both trolleys on the same step is counted once. Each step reads the previous step's table with four move combinations, and the answer is the state where both trolleys stand on the last tile.

Pythonentry point: round_trip_parcels

def round_trip_parcels(grid):
    # Time: O(n^3) -- there are 2n-1 lockstep steps and each pairs O(n) rows
    # with O(n) rows, with constant work per pair.
    # Space: O(n^2) for the row-pair table (two layers held at a time).
    n = len(grid)
    NEG = float("-inf")
    table = [[NEG] * n for _ in range(n)]
    table[0][0] = grid[0][0]
    for step in range(1, 2 * n - 1):
        nxt = [[NEG] * n for _ in range(n)]
        low = max(0, step - n + 1)
        high = min(n - 1, step)
        for r1 in range(low, high + 1):
            c1 = step - r1
            if grid[r1][c1] == -1:
                continue
            for r2 in range(r1, high + 1):
                c2 = step - r2
                if grid[r2][c2] == -1:
                    continue
                best = NEG
                for p1 in (r1 - 1, r1):
                    for p2 in (r2 - 1, r2):
                        if p1 < 0 or p2 < 0:
                            continue
                        a = p1 if p1 <= p2 else p2
                        b = p2 if p1 <= p2 else p1
                        if table[a][b] > best:
                            best = table[a][b]
                if best == NEG:
                    continue
                gain = grid[r1][c1]
                if r1 != r2:
                    gain += grid[r2][c2]
                if best + gain > nxt[r1][r2]:
                    nxt[r1][r2] = best + gain
        table = nxt
    final = table[n - 1][n - 1]
    return 0 if final == NEG else final

The obvious version

List every right-and-down route from corner to corner as a set of tiles, then try every ordered pair of routes and score the parcels in the union of the two tile sets, which is exactly what the round trip collects. Exponential in n, no table.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_round_trip_parcels(grid):
    n = len(grid)
    routes = []

    def walk(r, c, trail):
        if grid[r][c] == -1:
            return
        trail = trail + [(r, c)]
        if r == n - 1 and c == n - 1:
            routes.append(frozenset(trail))
            return
        if r + 1 < n:
            walk(r + 1, c, trail)
        if c + 1 < n:
            walk(r, c + 1, trail)

    walk(0, 0, [])
    if not routes:
        return 0
    best = 0
    for out_route in routes:
        for back_route in routes:
            total = 0
            for (r, c) in out_route | back_route:
                total += grid[r][c]
            if total > best:
                best = total
    return best

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in