LeetCode 1631 Path With Minimum Effort

概述

https://leetcode.com/problems/path-with-minimum-effort/

Dijkstra 算法

实现过程中犯的错：

1. 忘了应该用最小堆；
2. 没仔细看题，想当然认为 effort 是相加，没想到是求最大值；
3. 忘记给 d[0] 赋初值。

class Solution {
public:
    typedef pair<int, int> pi;
    int n = 0;
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size();
        n = heights[0].size();
        vector<vector<pair<int, int>>> graph(m * n);
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {                
                if (i != 0) graph[getIdx(i, j)].push_back({abs(heights[i][j] - heights[i-1][j]), getIdx(i-1, j)});
                if (j != 0) graph[getIdx(i, j)].push_back({abs(heights[i][j] - heights[i][j-1]), getIdx(i, j-1)});
                if (i != m - 1) graph[getIdx(i, j)].push_back({abs(heights[i][j] - heights[i+1][j]), getIdx(i+1, j)});
                if (j != n - 1) graph[getIdx(i, j)].push_back({abs(heights[i][j] - heights[i][j+1]), getIdx(i, j+1)});
            }
        }
        vector<int> d(m * n, INT_MAX);
        d[0] = 0;
        vector<bool> fixed(m * n, false);
        int c = 0;
        int targetIdx = m * n - 1;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            fixed[top.second] = true;
            if (top.second == targetIdx) break;
            
            for (auto& e : graph[top.second]) {
                if (!fixed[e.second]) {
                    if (d[e.second] > max(top.first, e.first)) {
                        d[e.second] = max(top.first, e.first);
                        pq.push({d[e.second], e.second});
                    }
                }
            }
        }
        return d[targetIdx];
    }
    
    int getIdx(int i, int j) {
        return i * n + j;
    }
};

Links: leetcode-1631-path-with-minimum-effort

未经允许，禁止转载，本文源站链接：https://iamazing.cn/