Longest Strictly Rising Four-Direction Walk in an Integer Grid

Given a grid of non-negative integers with m rows and n columns, return the number of cells on the longest walk whose values strictly increase from each cell to the next.

A walk may start at any cell. From each cell it moves to one of the four orthogonally adjacent cells: up, down, left or right. Diagonal moves are not allowed, and a walk may not leave the grid or wrap around its edges.

Function Signature

def longest_rising_walk(matrix: list[list[int]]) -> int:

Rules

• Every step must go to a cell whose value is strictly greater than the current cell's value. A step between equal values is not allowed.
• The length of a walk is the number of cells it visits. A single cell is a walk of length 1, so the answer is always at least 1.
• Because values strictly increase along a walk, no cell can be visited twice.
• Return only the maximum length. Several walks may share that length; the returned integer is the same either way.

Constraints

• m == len(matrix) and n == len(matrix[i]) for every row i
• 1 <= m <= 200 and 1 <= n <= 200
• 0 <= matrix[i][j] <= 2**31 - 1; every value fits in a 32-bit signed integer
• The answer is at most m * n, which is at most 40,000.

Examples

Example 1

Input: matrix = [[3, 1, 2, 5, 4]]
Output: 3

The walk 1 → 2 → 5 through columns 1, 2 and 3 visits three cells. Every other walk is shorter; for example, 1 → 3 and 4 → 5 visit two cells each.

Example 2

Input: matrix = [[7, 7], [7, 7]]
Output: 1

Every neighbor has an equal value, so no step is allowed and every walk is a single cell.

Example 3

Input: matrix = [
 [5, 1, 8],
 [4, 2, 7],
 [9, 3, 6]
]
Output: 6

Starting at the 1 in row 0, column 1, the walk 1 → 2 → 3 → 6 → 7 → 8 moves down, down, right, up and up, ending at row 0, column 2.