1631. 最小体力消耗路径

1631. 最小体力消耗路径

二分+搜索

bfs 搜索验证答案是否合法

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int minimumEffortPath(vector<vector<int>> &heights) {
        int n = heights.size(), m = heights[0].size();
        int left = 0, right = 1e6, res;

        while (left <= right) {
            int mid = left + right >> 1;
            queue<pair<int, int>> q;
            vector<bool> vis(n * m);
            q.emplace(0, 0);
            while (!q.empty()) {
                auto t = q.front();
                int x = t.first, y = t.second;
                q.pop();
                if (vis[x * m + y])continue;
                vis[x * m + y] = true;
                if (vis[n * m - 1])break;

                for (int i = 0; i < 4; i++) {
                    int a = x + dx[i], b = y + dy[i];
                    if (a >= 0 && a < n && b >= 0 && b < m && !vis[a * m + b] &&
                        abs(heights[a][b] - heights[x][y]) <= mid) {
                        q.emplace(a, b);
                    }
                }
            }

            if (vis[n * m - 1]) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
};

dijkstra

还是堆优化版的dijkstra

struct Edge {
    int x, y, z;

    bool operator<(const Edge &e) const {
        return z > e.z;
    }
};

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int minimumEffortPath(vector<vector<int>> &heights) {
        int n = heights.size(), m = heights[0].size();
        vector<bool> vis(n * m);
        vector<int> dist(n * m);

        priority_queue<Edge> q;
        q.push({0, 0, 0});
        while (!q.empty()) {
            auto[x, y, z]=q.top();
            q.pop();
            if (vis[x * m + y])continue;
            vis[x * m + y] = true;
            dist[x * m + y] = z;
            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && !vis[a * m + b]) {
                    q.push({a, b, max(z, abs(heights[x][y] - heights[a][b]))});
                }
            }
        }

        return dist[m * n - 1];
    }
};

并查集

「并查集」：我们可以将所有边按照长度进行排序并依次添加进并查集，直到左上角和右下角连通为止。

struct Edge {
    int x, y, z;

    bool operator<(Edge &e) {
        return z < e.z;
    }
};

class Solution {
public:
    vector<int> p;

    int find(int x) {
        if (p[x] != x)p[x] = find(p[x]);
        return p[x];
    }

    void merge(int a, int b) {
        p[find(a)] = find(b);
    }

    int minimumEffortPath(vector <vector<int>> &heights) {
        int n = heights.size(), m = heights[0].size();
        p.resize(n * m);
        for (int i = 0; i < p.size(); i++)p[i] = i;
        vector <Edge> edges;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int id = i * m + j;
                if (i) {
                    edges.push_back({id - m, id, abs(heights[i][j] - heights[i - 1][j])});
                }
                if (j) {
                    edges.push_back({id - 1, id, abs(heights[i][j] - heights[i][j - 1])});
                }
            }
        }

        sort(edges.begin(), edges.end());

        for (auto e:edges) {
            merge(e.x, e.y);
            if (find(0) == find(n * m - 1)) {
                return e.z;
            }
        }

        return 0;
    }
};