778. 水位上升的泳池中游泳

题目

在一个 N x N 的坐标方格grid中，每一个方格的值grid[i][j]表示在位置 (i,j) 的平台高度。

现在开始下雨了。当时间为t时，此时雨水导致水池中任意位置的水位为t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

示例

输入: [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

思路

由题意可知，t时间的水位高度为t，则某一个格的高度就是水恰好淹没该格的时间，也即“我们”能游到该格的最早时间。
从起点游到到终点的时间（因为游泳不消耗时间，其实只有从低格子到高格子的等待时间），就是通过路径中格子的最大高度。
由于游泳的方向不定，如果考虑格子则需要分类讨论。不如考虑边：

  • 行列各有n*(n-1)条边，需要两次双重循环遍历图得到所有的边。
  • 考虑可以通过该边的最早时间（能从一端游到另一端的最早时间），即为两端点高度的最大值。
  • 以三元组(i, j, arrival)的形式表示一条边。

算法过程类似Kruskal算法的思想：

  1. 首先对边按最早到达时间进行排序，然后依次选取最小的边。
  2. 在并查集中连接两点，若还未连通，则选取该边则并更新时间t为该边的最早到达时间。
  3. 当第一次起点和终点连通时，即退出，返回当前时间t。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class UnionFindSet
{
private:
    /* data */
    vector<int> parent, rank;

public:
    int size; // 总点数
    int extra; // 多余边条数
    int cp; // 连通分量个数
    UnionFindSet(int n);
    ~UnionFindSet();
    int find(int x);
    bool Union(int x, int y);
    void print();
    int getCP();
};

UnionFindSet::UnionFindSet(int n)
{
    extra = 0;
    cp = 0;
    size = n;
    rank.resize(n, 1);
    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

UnionFindSet::~UnionFindSet()
{
}

int UnionFindSet::find(int x) { //查询时路径压缩
    return parent[x] = parent[x] != x ? find(parent[x]) : parent[x];
}

bool UnionFindSet::Union(int x, int y) { //按秩合并
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        extra ++;
        return false;
    }
    if (rank[fx] < rank[fy]) {
        swap(fx, fy);
    }
    parent[fy] = fx;
    rank[fx] += rank[fy];
    return true;
}

void UnionFindSet::print() {
    for (int i = 0; i < size; i++) {
//        printf("%d -> %d\n", i, parent[i]);
         std::cout<<i<<" -> "<<parent[i]<<endl;
    }
}

int UnionFindSet::getCP() {
    for (int i = 0; i < size; i++) {
        if(parent[i] == i){
            cp++;
        }
    }
    return  cp;
}

class edge {
public:
    int i, j, arrival;
    edge(int _i, int  _j, int _arrival){
        i = _i; 
        j = _j;
        // arrival表示可通过该边的最早时间，取可到达两端点的时间的最大值，即高度的最大值
        arrival =  _arrival; 
    }
};

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int t = 0;
        UnionFindSet ufs(n*n);
        vector<edge> edges;
        for(int i=0;i<n;i++){ // 先算横边
            for(int j=0;j<n-1;j++){
                int index = n*i+j; // 二维映射到一维索引,先行后列;
                edges.emplace_back(index, index+1, max(grid[i][j], grid[i][j+1]));
            }
        }
        for(int j=0;j<n;j++){ // 再算纵边
            for(int i=0;i<n-1;i++){
                int index = n*i+j; // 二维映射到一维索引,先行后列
                edges.emplace_back(index, index+n, max(grid[i][j], grid[i+1][j]));
            }
        }
        // 按能通过该边的最早时间排序
        sort(edges.begin(), edges.end(), [](edge a, edge b) -> bool { 
            return a.arrival < b.arrival;
         });
        for(auto& [ni, nj, arrival]: edges){ // 依次选取代价最小的
            if(ufs.Union(ni, nj)) // 连接两点
            {
                t = max(arrival, t);
                if(ufs.find(n*n - 1) == ufs.find(0)){ // 若左上角与右下角连通
                    return t;
                }
            }        
        }
        return 0;
    }
};