This question evaluates a candidate's ability to reason about constrained grid reachability and efficient handling of multiple threshold queries, testing skills in reachability analysis, graph traversal concepts, and query-driven precomputation.
You are given:
m x n
integer matrix
terrain
.
limits
of length
k
.
For each query value L = limits[i], you start at the top-left cell (0, 0) and may move repeatedly to any 4-directionally adjacent cell (up/down/left/right).
Rules for scoring and movement:
(r, c)
only if
L
is
strictly greater
than
terrain[r][c]
.
Define answer[i] as the maximum number of points you can obtain for limits[i].
Return the array answer.
Function signature
int[][] terrain, int[] limits
int[] answer
Example 1
terrain = [
[1, 4, 2, 8],
[0, 4, 0, 8],
[1, 2, 0, 8]
]
limits = [8, 2]
answer = [9, 3]
Example 2
terrain = [
[2, 5, 7],
[3, 5, 1]
]
limits = [5, 6, 2]
answer = [5, 8, 1]
Notes:
k
is large (many queries).
terrain
values may repeat;
limits
are arbitrary integers.