题解 | 腐烂的苹果

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
      int move[5]={-1,0,1,0,-1};
    int rotApple(vector<vector<int> >& grid) {
       
        // write code here
        int l=0,r=0;
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<bool>>visited(n,vector<bool>(m,false));
        vector<vector<int>> q(n*m,vector<int>(2));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==2){
                    visited[i][j]=true;
                    q[r][0]=i;
                    q[r++][1]=j;
                }
            }
        }
        int levels=0;
        while(l<r){
            levels++;
            int sizes=r-l;
            for(int i=0,nx,ny,x,y;i<sizes;i++){
                x=q[l][0];
                y=q[l++][1];
                for(int k=0;k<4;k++){
                    nx=x+move[k];
                    ny=y+move[k+1];
                 if(nx>=0&&ny>=0&&nx<n&&ny<m&&!visited[nx][ny]){
                 if(grid[nx][ny]==1){//如果是好苹果就感染成功，并加入队列，也来感染
                       visited[nx][ny]=true;
                       grid[nx][ny]=2;
                       q[r][0]=nx;
                       q[r++][1]=ny;
                    }          
                    else if(grid[nx][ny]==0){//如果是空气就代表已经遍历过就行
                        visited[nx][ny]=true;
                    }
                }

                }
            }
        }
        //做完感染后，就遍历检查是否还有好苹果
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                 if(grid[i][j]==1)
                 return -1;
            }
        }
         return levels-1;
    }
};