Terrain Reach Score: Maximum Score Reachable on a Grid With Movement Constraints

Question

## Problem

You have an `m x n` grid where each cell has a height value. Starting from any cell in the top row, move down, left, or right (not up). You cannot move to a cell whose height difference from the current cell exceeds a threshold `t`. The score for a path is the sum of cell values visited. Return the maximum score reachable.

```python
def max_terrain_score(grid: list[list[int]], t: int) -> int:
    # grid[i][j] = height/score of cell
    # t = max allowed |height difference| between adjacent cells on path
    pass
```

**Example:**
```
grid = [[1,3,2],[4,2,5],[1,6,3]], t = 2
Output: 14  # path: (0,1)=3 -> (1,1)=2 -> (2,1)=6... adjust for valid moves
```

## Follow-ups

1. What DP recurrence did you use? What are the dimensions of the DP table?
2. If you can also move upward but only once per path, how does the state space change?
3. How would you reconstruct the actual path taken, not just the score?
4. If the grid is 10^4 x 10^4, what optimizations are necessary?

Terrain Reach Score: Maximum Score Reachable on a Grid With Movement Constraints

Question Details

Full Details

Topics

More from Uber