994. Rotting Oranges

问题：

橘子催熟问题，0:空地，1:新鲜橘子，2:成熟橘子

每一分钟成熟橘子会催熟四周的新鲜橘子，但如果新鲜橘子四周空着，则不会被催熟。

求给定数组情况，最多需要多久催熟所有的橘子，如果无法催熟所有则返回-1。

Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:
Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.
 

Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

　　

解法：

图的广度优先搜索BFS。需要queue来存储同一阶层所有节点。

同时进行更深一层搜索。

应用至本问题，先遍历所有节点，找到成熟橘子2的节点，存入queue中。

（可同时记录新鲜橘子 1 的个数cnt）

接着，对queue中该阶层的每个元素进行展开，展开层数res++

（由于之后不断加元素到queue，则需要记录当前queue的size，每进行size次后，则说明该展开下一阶层的queue）

对每一个元素节点，向四个方向催熟，如果为 1 ，则催熟至 2 ，同时加入queue中。（进行一个1->2的转化，则cnt--<剩下为1的橘子数>）

继续重复操作queue中所有元素，直到queue中为空。

那么，如果cnt!=0，则催熟动作完成后，还剩下cnt个新鲜橘子，无法催熟，那么返回-1

反之，则返回展开的层数res。

代码参考：

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int i, j, m, n, cnt=0, res=-1;
        queue<vector<int>> q;
        vector<vector<int>>dir={{-1,0},{1,0},{0,-1},{0,1}};
        n=grid.size();
        if(n==0) return 0;
        m=grid[0].size();
        for(i=0; i<n; i++){
            for(j=0; j<m; j++){
                if(grid[i][j]==1) cnt++;
                if(grid[i][j]==2) q.push({i,j});
            }
        }
        
        while(!q.empty()){
            res++;
            int qsize=q.size();
            for(int k=0; k<qsize; k++){
                vector<int> cur=q.front();
                q.pop();
                for(i=0; i<4; i++){
                    int x=cur[0]+dir[i][0], y=cur[1]+dir[i][1];
                    if(x<0 || x>=n || y<0 || y>=m || grid[x][y]!=1) continue;
                    grid[x][y]=2;
                    q.push({x,y});
                    cnt--;
                }
            }
        }
        if(cnt==0) return max(0,res);
        return -1;
    }
};