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 ```python 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** ```text 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** ```text 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** ```text 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.