778 Swim in Rising Water
778. Swim in Rising Water
1. Question
On an N x Ngrid
, each squaregrid[i][j]
represents the elevation at that point(i,j)
.
Now rain starts to fall. At timet
, the depth of the water everywhere ist
. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t
. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.
You start at the top left square(0, 0)
. What is the least time until you can reach the bottom right square(N-1, N-1)
?
Example 1:
Input:[[0,2],[1,3]]
Output:3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
Example 2:
Input: [[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:
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
The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Note:
2 <= N <= 50
.grid[i][j] is a permutation of [0, ..., N*N - 1].
2. Implementation
(1) Union Find
class Solution {
public int swimInWater(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int n = grid.length;
int time = 0;
UnionFind uf = new UnionFind(n * n);
while (!uf.isConnected(0, n * n - 1)) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] > time) continue;
if (i < n - 1 && grid[i + 1][j] <= time) {
uf.union(i * n + j, (i + 1) * n + j);
}
if (j < n - 1 && grid[i][j + 1] <= time) {
uf.union(i * n + j, i * n + j + 1);
}
}
}
++time;
}
return time - 1;
}
class UnionFind {
int[] parents;
int[] size;
public UnionFind(int n) {
parents = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
size[i] = 1;
}
}
public int find(int id) {
while (id != parents[id]) {
id = parents[id];
}
return id;
}
public boolean isConnected(int i, int j) {
return find(i) == find(j);
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI == rootJ) return;
if (size[rootI] < size[rootJ]) {
parents[rootI] = rootJ;
size[rootJ] += size[rootI];
}
else {
parents[rootJ] = rootI;
size[rootI] += size[rootJ];
}
}
}
}
3. Time & Space Complexity
Union Find: 时间复杂度O(n^2 * T), T为从(0, 0) 到(n - 1, n - 1)的时间, 空间复杂度O(n^2)
Last updated
Was this helpful?