Use a min-heap to always expand to the neighbor with the lowest elevation, similar to a modified Dijkstra.

Swim in Rising Water

hard

Acceptance: 43%

GraphsBFSDFS

An n-by-n grid of distinct elevations is given. As time progresses, the water level rises uniformly: at time t, any cell with elevation at most t is submerged and swimmable. You may travel between 4-directionally adjacent cells only if both are submerged. Determine the earliest time at which you can travel from the top-left cell to the bottom-right cell.

Examples

Example 1:

Input:grid = [[0,3],[2,1]]

Output:3

Explanation: At time 3, cells with elevation 0, 2, 1, and 3 are all submerged, enabling a path.

Example 2:

Input:grid = [[0,1,5],[2,3,4],[7,6,8]]

Output:6

Explanation: At time 6, a path exists through elevations at most 6 from (0,0) to (2,2).

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Swim in Rising Water

Examples

Hints

Related Problems