LeetCode 778. Swim in Rising Water

Posted on Edited on In 
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
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    UF(int _n): n(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y])
                swap(x, y);
            f[y] = x;
            size[x] += size[y];
        }
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int N = grid.size();
        vector<tuple<int, int, int>> edges;
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                int idx = r * N + c;
                if (r < N - 1) {
                    edges.emplace_back(idx, idx + N, max(grid[r + 1][c], grid[r][c]));
                }
                if (c < N - 1) {
                    edges.emplace_back(idx, idx + 1, max(grid[r][c + 1], grid[r][c]));
                }
            }
        sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, w1] = e1;
            auto&& [x2, y2, w2] = e2;
            return w1 < w2;
        });
        UF uf(N * N);
        int lastIdx = N * N - 1;
        for (const auto [x, y, w] : edges) {
            uf._union(x, y);
            if (uf.connected(0, lastIdx))
                return w;
        }
        return 0;
    }
};
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
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int N = grid.size();
        int left = 0, right = N * N - 1, ans = 0, dirs[] = {1, 0, -1, 0, 1};
        int lastIdx = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            vector<bool> seen(N * N);
            seen[0] = true;
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                for (int i = 0; i < 4;) {
                    int nr = r + dirs[i], nc = c + dirs[++i];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N || seen[nr * N + nc] 
                        || max(grid[nr][nc], grid[r][c]) > mid) continue;
                    q.emplace(nr, nc);
                    seen[nr * N + nc] = true;
                }
            }
            if (seen[lastIdx]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};
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
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int N = grid.size(), dirs[] = {1, 0, -1, 0, 1};
        auto tupleCmp = [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, h1] = e1;
            auto&& [x2, y2, h2] = e2;
            return h1 > h2;
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(tupleCmp)> q(tupleCmp);
        q.emplace(0, 0, grid[0][0]);
        vector<int> height(N * N, INT_MAX);
        height[0] = grid[0][0];
        vector<bool> seen(N * N);
        while (!q.empty()) {
            auto [r, c, h] = q.top(); q.pop();
            int idx = r * N + c;
            if (seen[idx]) continue;
            if (r == N - 1 && c == N - 1) break;
            seen[idx] = true;
            for (int i = 0; i < 4;) {
                int nr = r + dirs[i], nc = c + dirs[++i];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                int nh = max(h, grid[nr][nc]);
                if (nh >= height[nr * N + nc]) continue;
                height[nr * N + nc] = nh;
                q.emplace(nr, nc, nh);
            }
        }
        return height[N * N - 1];
    }
};