0847HardArrayDynamic ProgrammingMatrix

Richest Descent Through the Quarry

Tracked in this browser only

Trains the technique from

LeetCode 1301Number of Paths with Max Score

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 quarry face is a square grid of cells given as board, a list of equal-length strings. The cell in the bottom right corner holds 'S', the start, and the cell in the top left corner holds 'E', the exit. Every other cell holds either a digit '1' through '9', which is the ore it yields, or 'X', which is impassable.

A hauler starts on 'S' and must reach 'E', moving each step to the cell directly above, directly to the left, or diagonally up and to the left. It may never enter an 'X' cell. The haul of a route is the total ore of the cells it enters, counting neither 'S' nor 'E', which yield nothing.

Return a list of two numbers: the largest haul any route can collect, and how many routes collect it, that count taken modulo 1000000007. If no route reaches the exit at all, return [0, 0].

Examples

Example 1

Input: board = ["E23", "2X2", "12S"]
Output: [7, 1]

One route runs from the start up to the 2 above it, then up to the 3, then left twice to the exit, gathering 2 + 3 + 2 = 7. Another gathers the same total by a different set of cells.

Example 2

Input: board = ["EX", "XS"]
Output: [0, 1]

Both cells beside the start are impassable and the diagonal step lands on the exit, so no route reaches it and the answer is [0, 0].

Example 3

Input: board = ["E1", "1S"]
Output: [1, 2]

The hauler can step up then left, or left then up, each gathering the single 1 on the way, or take the diagonal step straight to the exit gathering nothing. The largest haul is 1 and two routes collect it.

Constraints

2 <= board.length <= 100
Every string of board has the same length as board.length
board[i][j] is one of 'S', 'E', 'X' or a digit from '1' to '9'
board[board.length - 1][board.length - 1] is 'S' and board[0][0] is 'E'

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 richest_descent(board: list[str]) -> list[int]:

Java

public int[] richestDescent(List<String> board)

The intended approach

Time O(n^2) for an n by n face: constant work per cell.Space O(n^2) for the two tables.

Every move takes the hauler up, left, or both, so a route never revisits a cell and the cells can be settled in order from the start corner outwards. Keep two tables: the best haul reachable from the start to each cell, and how many routes achieve it. A cell inherits from the three cells a step behind it, taking the largest haul among them and adding together the route counts of those that tie, then adding its own ore. Impassable cells and cells nothing can reach stay unset so they never contribute. The exit's own entry is the answer, with the route count reduced.

Pythonentry point: richest_descent

def richest_descent(board):
    MOD = 10 ** 9 + 7
    n = len(board)
    NEG = -1
    # haul[r][c] is the best ore total from the start corner to this cell, and
    # ways[r][c] how many routes achieve it; NEG means unreachable
    haul = [[NEG] * n for _ in range(n)]
    ways = [[0] * n for _ in range(n)]
    haul[n - 1][n - 1] = 0
    ways[n - 1][n - 1] = 1
    for r in range(n - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            if r == n - 1 and c == n - 1:
                continue
            ch = board[r][c]
            if ch == "X":
                continue
            best = NEG
            count = 0
            for dr, dc in ((1, 0), (0, 1), (1, 1)):
                pr = r + dr
                pc = c + dc
                if pr >= n or pc >= n:
                    continue
                if haul[pr][pc] == NEG:
                    continue
                if haul[pr][pc] > best:
                    best = haul[pr][pc]
                    count = ways[pr][pc]
                elif haul[pr][pc] == best:
                    count = (count + ways[pr][pc]) % MOD
            if best == NEG:
                continue
            gain = 0 if ch == "E" else int(ch)
            haul[r][c] = best + gain
            ways[r][c] = count % MOD
    if haul[0][0] == NEG:
        return [0, 0]
    return [haul[0][0], ways[0][0] % MOD]

The obvious version

Walk every route from the start corner to the exit with an explicit stack, adding up the ore of each one, then report the largest total and how many routes reached it. Exponential in the face size, but it never reasons about settling cells in order.

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_richest_descent(board):
    MOD = 10 ** 9 + 7
    n = len(board)
    best = None
    count = 0
    stack = [(n - 1, n - 1, 0)]
    while stack:
        r, c, got = stack.pop()
        if r == 0 and c == 0:
            if best is None or got > best:
                best = got
                count = 1
            elif got == best:
                count += 1
            continue
        for dr, dc in ((-1, 0), (0, -1), (-1, -1)):
            nr = r + dr
            nc = c + dc
            if nr < 0 or nc < 0:
                continue
            ch = board[nr][nc]
            if ch == "X":
                continue
            gain = 0 if ch == "E" else int(ch)
            stack.append((nr, nc, got + gain))
    if best is None:
        return [0, 0]
    return [best, count % MOD]

How this problem was checked

Reference solution executed against 13 test cases — 13 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