Show problems as
Classic problem #1301HardArrayDynamic ProgrammingMatrix

Number of Paths with Max Score

Real-world version: Richest Descent Through the Quarry
Tracked in this browser only
Read Number of Paths with Max Score on LeetCode(opens in a new tab)

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

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

Python
def richest_descent(board: list[str]) -> list[int]:
Java
public int[] richestDescent(List<String> board)

More on the same topics