994.腐烂的橘子 (Easy)*

题目描述*

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例*

输入：[[2,1,1],[1,1,0],[0,1,1]]

输出：4

输入：[[2,1,1],[0,1,1],[1,0,1]] 输出：-1

代码*

最简单的是用暴力，不过每次会重复遍历内部的坏结点。使用 bfs，将坏结点入队，好结点加入集合，每次将坏结点出队，将周围好结点入队，并从集合中去除，最后如果好结点集合为空，则成功全部感染。

暴力bfs

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int goodCnt = 0, badCnt = 0;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                goodCnt += (grid[i][j] == 1);
                badCnt += (grid[i][j] == 2);
            }
        }
        if(goodCnt == 0) {
            return 0;
        }
        if(badCnt == 0) {
            return -1;
        }
        int res = 0;
        int curGood = goodCnt;
        while(curGood) {
            res++;
            for(int i = 0; i < grid.size(); i++) {
                for(int j = 0; j < grid[0].size(); j++) {
                    if(grid[i][j] == 2) {
                        if(i != 0 && grid[i - 1][j] == 1) {
                            grid[i - 1][j] = 3;
                            curGood--;
                        }
                        if(i != grid.size() - 1 && grid[i + 1][j] == 1) {
                            grid[i + 1][j] = 3;
                            curGood--;
                        }
                        if(j != 0 && grid[i][j - 1] == 1) {
                            grid[i][j - 1] = 3;
                            curGood--;
                        }
                        if(j != grid[0].size() - 1 && grid[i][j + 1] == 1) {
                            grid[i][j + 1] = 3;
                            curGood--;
                        }
                    }
                }
            }
            for(int i = 0; i < grid.size(); i++) {
                for(int j = 0; j < grid[0].size(); j++) {
                    if(grid[i][j] == 3) {
                        grid[i][j] = 2;
                    }
                }
            }
            if(curGood == goodCnt) {
                return -1;
            }
            goodCnt = curGood;
        }
        return res;
    }
};

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size();
        if(rows == 0) {
            return 0;
        }
        int cols = grid[0].size();
        queue<pair<int, int>> rot;
        set<pair<int, int>> good;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(grid[i][j] == 1) {
                    good.insert({i, j});
                }else if(grid[i][j] == 2){
                    rot.push({i, j});
                }
            }
        }
        int res = 0;
        vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(!rot.empty()) {
            int len = rot.size();
            bool flag = false;
            for(int i = 0; i < len; i++) {
                int x = rot.front().first, y = rot.front().second;
                rot.pop();
                for(auto j : dirs) {
                    auto tmp = make_pair(x + j.first, y + j.second);
                    if(good.find(tmp) != good.end()) {
                        good.erase(tmp);
                        rot.push(tmp);
                        flag = true;
                    }
                }
            }
            res += flag;
        }
        if(!good.empty()) {
            return -1;
        }
        return res;
    }
};

最后更新: July 23, 2022