778. Swim in Rising Water

问题：

给定一个N*N正方形区域的海拔。

一个人从[0,0]起向终点[N,N]前进，

下雨每单位时间，下一单位海拔的水。

只有当人所在周围的水位上升到海拔的位置，这个人才能向周围游动。

求要到达终点，至少要经过多长时间。（不考虑游泳速度。只考虑下雨海拔满足的时间）

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].

解法：

解法一：并查集（Disjoint Set）

使用 i*N+j。代表某个坐标点。作为并查集操作对象。

每次判断：起点[0,0]终点[N,N]是否联通

若没有：遍历正方形所有区域，

若某个点的grid值<当前时间res

则判断其右边和下面的点，是否也<当前时间res，则说明此时水的海拔已经漫过这些点，将这些点merge

每次时间递增res++

代码参考：

 1 class Solution {
 2 public:
 3     int swimInWater(vector<vector<int>>& grid) {
 4         int N=grid.size();
 5         DisjointSet DS(N*N);
 6         int res=0;
 7         while(!DS.isConnected(0, N*N-1)) {
 8             for(int i=0; i<N; i++) {
 9                 for(int j=0; j<N; j++) {
10                     if(grid[i][j]>res) continue;
11                     if(i+1 < N && grid[i+1][j] <= res) DS.merge(N*i+j, N*(i+1)+j);
12                     if(j+1 < N && grid[i][j+1] <= res) DS.merge(N*i+j, N*i+j+1);
13                 }
14             }
15             res++;
16         }
17         return res-1;
18     }
19 };

并查集类代码参考：

 1 class DisjointSet {
 2 public:
 3     DisjointSet(int n):root(n,0), rank(n,0) {
 4         for(int i=0; i<n; i++) {
 5             root[i]=i;
 6         }
 7     }
 8     int find(int i) {
 9         if(root[i]!=i) {
10             root[i] = find(root[i]);
11         }
12         return root[i];
13     }
14     bool merge(int x, int y) {
15         int x_root=find(x);
16         int y_root=find(y);
17         if(x_root==y_root) return false;
18         if(rank[x_root] > rank[y_root]) {
19             root[y_root] = x_root;
20         } else if(rank[y_root] > rank[x_root]) {
21             root[x_root] = y_root;
22         } else {
23             root[y_root] = x_root;
24             rank[x_root]++;
25         }
26         return true;
27     }
28     bool isConnected(int x, int y) {
29         int x_root=find(x);
30         int y_root=find(y);
31         return x_root==y_root;
32     }
33 private:
34     vector<int> root;
35     vector<int> rank;
36 };