> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/778-swim-in-rising-water.md).

# 778     Swim in Rising Water

## 778. [Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/description/)

## 1. Question

On an N x N`grid`, each square`grid[i][j]`represents the elevation at that point`(i,j)`.

Now rain starts to fall. At time`t`, the depth of the water everywhere is`t`. 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:**

1. `2 <= N <= 50`.
2. grid\[i]\[j] is a permutation of \[0, ..., N\*N - 1].

## 2. Implementation

**(1) Union Find**

```java
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)