leetcode-cpp 994.腐爛的橘子

994.腐爛的橘子

• 題目：

• 連結

  leetcode

• solution:

  胡爛的橘子

  有點像那個染色問題

  BFS 感覺難點在于怎麼判斷還能不能腐爛橘子 寫了一堆又臭又長的代碼…

  ps：學會了一個東西 就是需要取上下左右值的時候 可以寫一個數組{{1,0},{-1,0},{0,1},{0,-1}}

  然後先計算 再判斷是否超界 比一層一層的判斷之後再計算好

• code

class Solution {
public:
//BFS!!!!!!!!!!!!!!!!!!!!!!!!!!!
    int orangesRotting(vector<vector<int>>& grid) {
        if(grid.size()==0||grid[0].size()==0) return -1;
        queue<pair<int,int>>q;
        int count=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]!=0) count++;
                if(grid[i][j]==2)
                q.push(make_pair(i,j));      
            }
        }
        int time=0;
        if(count==q.size()) return 0;
    vector<pair<int,int>>ms={{1,0},{-1,0},{0,1},{0,-1}};
    while(!q.empty()){
        int len=q.size();
        time++;
        while(len--){
            auto t=q.front();
            q.pop();
            for(auto m:ms){
                int x=t.first+m.first;
                int y=t.second+m.second;//pair<>is a good tool
                if(x<0||x>=grid.size()||y<0||y>=grid[0].size()) continue;//以後遇到這樣用，就不用每次浪費if一大堆了
                //pair是個好東西
                if(grid[x][y]==1){
                    grid[x][y]=2;
                    q.push(make_pair(x,y));
                }
            }
        }
    }
    for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                //if(grid[i][j]!=0) count++;
                if(grid[i][j]==1)
                return -1;      
            }
        }
    return time-1;
    }
};