一、題目

文章來源地址http://www.zghlxwxcb.cn/news/detail-826952.html

二、思路

• 首先將所有爛橘子入隊，然后常規(guī)BFS遍歷，注意while的截止條件除了隊列為空，新鮮橘子數(shù)量大于0（沒新鮮橘子也沒必要繼續(xù)遍歷，保證時間計算的正確性），這兩者一個不滿足就可以停止
• 每分鐘進行一次【腐爛擴散】，使用BFS對二維圖進行遍歷，注意和二叉樹的層次遍歷不一樣（二叉樹則是只有一個根節(jié)點，這里可能有多個腐爛橘子-根節(jié)點）。
• auto [x, y] = q.front()是C++17引入的新語法，結(jié)構(gòu)化綁定，可以從數(shù)組、元組或結(jié)構(gòu)體中一次性解包多個值，并將他們綁定到多個變量上，比如這里就是聲明了x和y變量，然后將這2個變量綁定到元組中。如果不這么使用，可以直接通過first和second訪問pair元素的數(shù)值。
• auto& dir: directions是C++11的語法，&表示引用，直接auto dir則是按值訪問，前者可以避免不必要的復(fù)制，并且允許你修改容器的容器。

三、代碼

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        //存儲上下左右的坐標方位
        vector<pair<int, int>> directions = {{0,1}, {0,-1}, {1,0},{-1,0}};
        int fresh_num = 0;
        //創(chuàng)建隊列，存儲腐爛的橘子二維坐標位置
        queue<pair<int, int>>q;
        for(int i=0; i < m;i++){
            for(int j=0; j < n; j++){
                if (grid[i][j] == 1)
                    fresh_num += 1;
                //將所有爛橘子入隊列
                if (grid[i][j] == 2)
                    q.push({i, j});
            }
        }
        int minutes = 0;
        //爛橘子隊列中沒有橘子后則停止
        while(!q.empty() && fresh_num > 0){
            int q_num = q.size();
            //所有的爛橘子同時開始干活
            for(int i=0; i< q_num; i++){ 
                //隊首元素
                pair<int, int>one = q.front();
                q.pop(); //出隊
                int x = one.first;
                int y = one.second;
                //遍歷當前位置的上下左右
                for(auto& dir: directions){
                    int nx = x + dir.first;
                    int ny = y + dir.second;
                    if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1){ //如果是新鮮橘子
                        grid[nx][ny] = 2;
                        q.push({nx, ny});
                        fresh_num -= 1;
                    }
                }
            }
            minutes += 1;
        }
        return fresh_num == 0?minutes:-1;
    }
};

到了這里，關(guān)于【leetcode994】腐爛的橘子（BFS）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！