题解 | #腐烂的苹果#

class Solution {//多源bfs
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */

    int rotApple(vector<vector<int> >& grid) {
        
        int n = grid.size();
        int m = grid[0].size();
        int que[n*m+1][2];//队列苹果
        int a = 0; //完好苹果个数
        int tail = 0; //
        int mins = 0; //result mins
        int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1}; //上下左右
        for (int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                a += 1;//统计初始完好总数
            } else if (grid[i][j] == 2) {
                que[tail][0] = i;
                que[tail++][1] = j;
            }
        }
        int head=0;
        int tag=1;
        int temp=0;
        vector<vector<int>> vis(n,vector<int>(m));
        int flag=0;//
        int testx=0;
        int testy=0;
        while (head<tail && a>0) {
            temp = tail;
            tag=0;
            while (head < temp) {
                int x = que[head][0];
                int y = que[head++][1];
                for (int i=0;i<4;i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || ny < 0 || nx > n - 1 || ny > m - 1) {
                        continue;
                    }
                    if (grid[nx][ny] == 1 && vis[nx][ny] == 0) {
                        tag = 1;
                        flag=1;//
                        que[tail][0] = nx;
                        que[tail++][1] = ny;
                        vis[nx][ny]=1;//aff
                        grid[nx][ny]=2;
                        a=a-1;
                    }
                }
            }
            if(tag){mins+=1;
            }
        }
        if(a>0){
            return -1;
        }
        else{
            return mins;
        }
    }
};