题解 | #腐烂的苹果#

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

    int rotApple(vector<vector<int> >& grid) {
        // write code here
        deque<int> queue_;
        unordered_set<int> used;
        int n = grid.size();
        int m = grid[0].size();
        int num = 0; //记录当前格子中完好的苹果个数
        //将腐烂苹果的相邻完好苹果存入队列中
        //used为了防止同一个完好苹果多次被存入队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    // used.insert(i*m + j);
                    if (i > 0 && grid[i - 1][j] == 1 && used.count((i - 1)*m + j) == 0) {
                        queue_.push_back((i - 1)*m + j);
                        used.insert((i - 1)*m + j);
                    }
                    if (j > 0 && grid[i][j - 1] == 1 && used.count(i * m + j - 1) == 0) {
                        queue_.push_back(i * m + j - 1);
                        used.insert(i * m + j - 1);
                    }
                    if (i < n - 1 && grid[i + 1][j] == 1 && used.count((i + 1)*m + j) == 0) {
                        queue_.push_back((i + 1)*m + j);
                        used.insert((i + 1)*m + j);
                    }
                    if (j < m - 1 && grid[i][j + 1] == 1 && used.count(i * m + j + 1) == 0) {
                        queue_.push_back(i * m + j + 1);
                        used.insert(i * m + j + 1);
                    }
                } else if (grid[i][j] == 1) {
                    num++;
                }
            }
        }
        int turn = 0;//经过几轮 达到峰值
        while (!queue_.empty()) {
            int sz = queue_.size();
            turn++;
            for (int k = 0; k < sz; k++) {
                int tmp = queue_.front();
                queue_.pop_front();
                int i = tmp / m;
                int j = tmp % m;
                grid[i][j] = 2; //该苹果腐烂
                if (i > 0 && grid[i - 1][j] == 1 && used.count((i - 1)*m + j) == 0) {
                    queue_.push_back((i - 1)*m + j);
                    used.insert((i - 1)*m + j);
                }
                if (j > 0 && grid[i][j - 1] == 1 && used.count(i * m + j - 1) == 0) {
                    queue_.push_back(i * m + j - 1);
                    used.insert(i * m + j - 1);
                }
                if (i < n - 1 && grid[i + 1][j] == 1 && used.count((i + 1)*m + j) == 0) {
                    queue_.push_back((i + 1)*m + j);
                    used.insert((i + 1)*m + j);
                }
                if (j < m - 1 && grid[i][j + 1] == 1 && used.count(i * m + j + 1) == 0) {
                    queue_.push_back(i * m + j + 1);
                    used.insert(i * m + j + 1);
                }
            }
        }
        if (num != used.size()) return -1;
        else return turn;
        }
};