Flood Navigation Minimum Time

HARD40 pts

You are given an n × n grid representing a terrain map, where each cell terrain[i][j] contains a distinct non-negative integer representing the elevation level at position (i, j).

A flood simulation is occurring where the water level rises uniformly across the entire terrain over time. At any time unit t, the water level equals t, meaning any cell with an elevation less than or equal to t becomes submerged and thus traversable by swimming.

You are positioned at the top-left corner (0, 0) and need to reach the bottom-right corner (n-1, n-1). Movement is allowed in the four cardinal directions (up, down, left, right) to adjacent cells, but you can only move between two cells if both cells have elevations that do not exceed the current water level t. Swimming between traversable cells is instantaneous—there is no additional time cost for movement itself.

Your task: Determine the minimum time required for the water level to rise sufficiently such that a path exists from the starting position to the destination.

Key observations:

At time t = 0, only cells with elevation 0 can be accessed.
You must wait for enough cells to become submerged to form a connected path.
The answer will be the maximum elevation encountered along the optimal path from start to finish.

Example

Input

terrain = [[0,2],[1,3]]

Output

3

Explanation

At t=0, only position (0,0) with elevation 0 is accessible. We cannot move to neighbors since (0,1)=2 and (1,0)=1 require higher water levels. At t=1, we can access (1,0). At t=2, we can access (0,1). At t=3, the water level finally reaches (1,1)=3, completing a path from (0,0) to (1,1). The minimum time is 3.

Example

Input

terrain = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

Output

16

Explanation

The optimal path follows the perimeter: (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(3,4)→(4,4). This path has a maximum elevation of 16 at position (2,4). Alternative paths through the center have higher maximum elevations (23, 22, etc.), so we need to wait only until t=16.

Example

Input

terrain = [[0,1,2],[3,4,5],[6,7,8]]

Output

8

Explanation

In this grid with strictly increasing elevations, any path from (0,0) to (2,2) must pass through the destination cell (2,2) which has elevation 8. Therefore, the minimum time required is 8.

Accepted0/0·0% Acceptance

Constraints

n == terrain.length
n == terrain[i].length
1 ≤ n ≤ 50
0 ≤ terrain[i][j] < n²
Each value in terrain is unique (no duplicate elevations).

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

grid =

[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

Flood Navigation Minimum Time

Hints

Flood Navigation Minimum Time

Hints