Compute max reachable cells per threshold
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given:
- An `m x n` integer matrix `terrain`.
- An integer array `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:
- You are allowed to step onto a cell `(r, c)` **only if** `L` is **strictly greater** than `terrain[r][c]`.
- The **first time** you visit an allowed cell, you gain **1 point**.
- You may revisit cells any number of times, but you do **not** gain additional points for revisits.
- The process effectively ends when no additional moves to allowed (unvisited or visited) cells are possible under the rule above.
Define `answer[i]` as the **maximum number of points** you can obtain for `limits[i]`.
Return the array `answer`.
**Function signature**
- Input: `int[][] terrain, int[] limits`
- Output: `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:
- You should aim for an efficient solution when `k` is large (many queries).
- `terrain` values may repeat; `limits` are arbitrary integers.
Quick Answer: 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.