讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

展开讨论
力扣 (LeetCode)发起于 2020-03-01

第四题利用dijstra最短路径求解:

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        const int MAX = 1000000;
        int m = grid.size();
        int n = grid.front().size();
        vector<int> dis = vector<int>(m * n, MAX);
        dis[0] = 0;
        auto cmp = [](vector<int>& a, vector<int>&b){ return a[0] > b[0];};
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp) > pq(cmp);
        set<int> fixedP;
        pq.push({0, 0});
        while(pq.size() > 0){
            vector<int> temp = pq.top();
            pq.pop();
            if(fixedP.count(temp[1])){
                continue;
            }
            fixedP.insert(temp[1]);
            int r = temp[1] / n;
            int c = temp[1] % n;
            int d = grid[r][c];
            
            auto func = [&](int r, int c, int dd){ 
                if( r >= 0 && r < m && c >= 0 && c < n){
                    int p = r * n + c;
                    if(!fixedP.count(p)){
                        int disTmp = dis[temp[1]];
                        if(d != dd){
                            ++disTmp;
                        }
                        if(disTmp < dis[p]){
                            dis[p] = disTmp;
                            pq.push({disTmp, p});
                        }
                    }
                }
            };
            
            func(r - 1, c, 4);
            func(r + 1, c, 3);
            func(r, c - 1, 2);
            func(r, c + 1, 1);
        }
        return dis.back();
    }
};
展开全部 21 讨论