Show problems as
Classic problem #3742MediumArrayDynamic ProgrammingMatrix

Maximum Path Score in a Grid

Real-world version: Courier Rack Capacity
Tracked in this browser only
Read Maximum Path Score in a Grid on LeetCode(opens in a new tab)

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

A courier drives across a district laid out as m streets by n avenues. grid[i][j] is how many parcels are waiting at the corner on street i and avenue j. The depot sits at corner (0, 0) and has nothing waiting, and the sorting hall sits at corner (m - 1, n - 1).

From a corner the van may drive only to the next avenue, (i, j + 1), or to the next street, (i + 1, j). Whenever the van stands at a corner it must take every parcel waiting there, including at the depot and at the sorting hall, so a route's load is the total of the values of the corners it stands at.

The van's rack holds at most k parcels, so a route is drivable only when its load is at most k. Return the largest load of a drivable route, or -1 when every route from the depot to the sorting hall overloads the rack. A load is never negative, so -1 cannot be confused with a real load.

Examples

Example 1

Input
grid = [[0, 2, 0, 0], [0, 0, 0, 2]], k = 3
Output
2

Driving to the second street straight away and then along it stands at corners holding 0, 0, 0, 0 and 2 parcels, so that route loads 2 parcels and fits a rack of 3.

Example 2

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

There are only two routes across this district, and each of them stands at two corners holding 2 parcels, so each loads 4 parcels and neither fits a rack of 1.

Example 3

Input
grid = [[0, 2, 1, 0, 2], [1, 0, 2, 1, 0], [2, 1, 0, 2, 1]], k = 6
Output
6

Driving along the first street to its end and then down the last avenue stands at corners holding 0, 2, 1, 0, 2, then 0 and 1, so that route loads 6 parcels and exactly fills the rack.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 2
  • grid[0][0] == 0
  • 0 <= k <= 10^3

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 best_rack_load(grid: list[list[int]], k: int) -> int:
Java
public int bestRackLoad(int[][] grid, int k)

More on the same topics