LeetCode 1631. Path With Minimum Effort

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 minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size();
        vector<tuple<int, int, int>> edges;
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c) {
                int idx = r * C + c;
                if (r < R - 1) {
                    edges.emplace_back(idx, idx + C, abs(heights[r + 1][c] - heights[r][c]));
                }
                if (c < C - 1) {
                    edges.emplace_back(idx, idx + 1, abs(heights[r][c + 1] - heights[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(R * C);
        int lastIdx = R * C - 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
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size();
        int left = 0, right = 999999, ans = 0, lastIdx = R * C - 1, dirs[] = {1, 0, -1, 0, 1};
        while (left <= right) {
            int mid = (left + right) / 2;
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            vector<bool> seen(R * C);
            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 >= R || nc < 0 || nc >= C || seen[nr * C + nc] 
                        || abs(heights[nr][nc] - heights[r][c]) > mid) continue;
                    q.emplace(nr, nc);
                    seen[nr * C + 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 minimumEffortPath(vector<vector<int>>& heights) {
        const int R = heights.size(), C = heights[0].size(), dirs[] = {1, 0, -1, 0, 1};
        auto tupleCmp = [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, d1] = e1;
            auto&& [x2, y2, d2] = e2;
            return d1 > d2;
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(tupleCmp)> q(tupleCmp);
        q.emplace(0, 0, 0);
        vector<int> dist(R * C, INT_MAX);
        dist[0] = 0;
        vector<bool> seen(R * C);
        while (!q.empty()) {
            auto [r, c, d] = q.top(); q.pop();
            int idx = r * C + c;
            if (seen[idx]) continue;
            if (r == R - 1 && c == C - 1) break;
            seen[idx] = true;
            for (int i = 0; i < 4;) {
                int nr = r + dirs[i], nc = c + dirs[++i];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                int nd = max(d, abs(heights[r][c] - heights[nr][nc]));
                if (nd >= dist[nr * C + nc]) continue;
                dist[nr * C + nc] = nd;
                q.emplace(nr, nc, dist[nr * C + nc]);
            }
        }
        return dist[R * C - 1];
    }
};