Leetcode 994.腐烂的橘子【C++】

本文最后更新于:2020年11月19日 上午

地址:https://leetcode-cn.com/problems/rotting-oranges/

题目

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

值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

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

示例 1:

输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4

示例 2:

输入:[[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。

示例 3:

输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0

提示:

  • 1 <= grid.length <= 10
  • 1 <= grid[0].length <= 10
  • grid[i][j] 仅为 0、1 或 2

解题思路(1)

笨办法,先记录一下吧😅(内存消耗 :15.2 MB, 在所有 C++ 提交中击败了5.40%的用户)

我不确定有没有不用模拟橘子被感染的办法,如果有的话我觉得应该会更好一些。我一上来想到的就是模拟橘子被感染的整个过程,所以需要逐个橘子判断它的当前状态,然后判断它的上下左右的橘子的状态,如果存在需要感染的情况就修改某个橘子的状态。

我定义了一个同样大小的二维数组用来作为状态记录表(这里是主要占用内存的地方),初始化为全0,其中的整数即表示分钟数

另外定义了一个函数用于判断橘子是否全部腐烂,或者还有橘子可以被感染,或是存在不可能被感染的橘子。

代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int minute = 0;
        size_t rows = grid.size();//行数
        size_t cols = grid[0].size();//列数
        vector<int> temp(cols);//仅用于初始化状态记录表
        vector<vector<int>> record(rows, temp);//状态记录表,初始化为全0,数字0,1,2表示第0,1,2步
        
        //模拟橘子随时间被感染
        while (isInfectionOver(grid) == 1)
        {
            minute++;//分钟数+1
            //同步遍历橘子网格与状态记录表
            for (size_t i = 0; i < rows; i++) {
                for (size_t j = 0; j < cols; j++) {
                    if (grid[i][j] == 2 && record[i][j] < minute) {
                        record[i][j] = minute;
                        //感染上侧橘子
                        if (i > 0 && grid[i - 1][j] == 1) {
                            grid[i - 1][j] = 2;
                            record[i - 1][j] = minute;
                        }
                        //感染下侧橘子
                        if (i < rows - 1 && grid[i + 1][j] == 1) {
                            grid[i + 1][j] = 2;
                            record[i + 1][j] = minute;
                        }
                        //感染左侧橘子
                        if (j > 0 && grid[i][j - 1] == 1) {
                            grid[i][j - 1] = 2;
                            record[i][j - 1] = minute;
                        }
                        //感染右侧橘子
                        if (j < cols - 1 && grid[i][j + 1] == 1) {
                            grid[i][j + 1] = 2;
                            record[i][j + 1] = minute;
                        }
                    }
                }

            }
        }
        return isInfectionOver(grid) == 2 ? -1 : minute;
    }

    //是否感染结束,可能的返回值为0,1,2
    //0表示所有橘子都已腐烂;1表示仍存在可以被感染的橘子;2表示存在不可能被感染的橘子
    int isInfectionOver(vector<vector<int>>& grid) {
        int ret = 0;//作为返回值
        size_t rows = grid.size();//行数
        size_t cols = grid[0].size();//列数
        for (size_t i = 0; i < grid.size(); i++) {
            for (size_t j = 0; j < grid[i].size(); j++) {
                //只需判断表中的新鲜橘子是否可能被感染
                if (grid[i][j] == 1) {
                    ret = 2;//此处默认这个橘子不可能被感染
                    //上侧有腐烂橘子
                    if (i > 0 && grid[i - 1][j] == 2)
                        return 1;
                    //下侧有腐烂橘子
                    if (i < rows - 1 && grid[i + 1][j] == 2)
                        return 1;
                    //左侧有腐烂橘子
                    if (j > 0 && grid[i][j - 1] == 2)
                        return 1;
                    //右侧有腐烂橘子
                    if (j < cols - 1 && grid[i][j + 1] == 2)
                        return 1;
                }
            }
        }
        return ret;
    }
};

解题思路(2)

其实不是我自己想出来的这个解法~这是我自己用上面的思路解出来后,本来想自己优化一下上面的代码,结果改来改去反而不能正常运行了……然后我才去看了别人的题解,其中看了这个,思路比较简单,然后我觉得有些地方挺有亮点的,所以就自己复现了一遍。

将腐烂的橘子和新鲜橘子分了两类,腐烂的橘子用一个 queue<pair<int, int>> 类型的队列存储坐标,新鲜橘子只统计其个数。需要记录每分钟橘子开始腐烂前的腐烂的橘子的个数 n ,即处理完这n个腐烂的橘子分钟数才+1,逐个判断队列头的腐烂橘子周围是否有新鲜橘子需要感染,如果有就将这个新鲜橘子置为 2 即这个橘子已腐烂,将新腐烂的橘子的坐标加入到队列,并将新鲜橘子的个数-1。此外,还需要注意某一分钟内的n个腐烂橘子是否真的有感染周围的新鲜橘子,如果并没有感染任何新鲜橘子,那么分钟数是不应该增加的。直到所有的队列中的腐烂橘子处理完毕,跳出循环,此时如果新鲜橘子个数为0,即所有橘子均已腐烂,返回分钟数;若剩余新鲜橘子个数大于0,则说明存在不可能被感染的橘子,此时返回 -1。

几个值得学习的亮点:

  1. pair<int, int> 来记录二维数组的横纵坐标。真的很方便,简直量身定做吖;
  2. 用队列了处理腐烂的橘子。已处理过的橘子只需从队列头弹出,完美避免重复工作;
  3. vector<pair<int, int>> around = { {-1,0},{1,0},{0,-1},{0,1} }; 来对 grid[i][j] 上下左右相邻的位置进行处理。很巧妙的办法,因为 grid[i][j] 的横纵坐标 {i,j} 分别加上 {-1,0},{1,0},{0,-1},{0,1} 后即为上下左右相邻四个位置的横纵坐标,只需写一个循环即可处理四种情况,而不用对四种情况进行单独判断(比如解题思路(1)中我的代码😅)。

代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> rottenQueue;//保存腐烂橘子坐标的队列
        int fresh = 0;//剩余新鲜橘子的个数
        //统计
        for (size_t i = 0; i < grid.size(); i++) {
            for (size_t j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 2)
                    rottenQueue.push({ i, j });
                if (grid[i][j] == 1)
                    fresh++;
            }
        }

        int minute = 0;//分钟数
        vector<pair<int, int>> around = { {-1,0},{1,0},{0,-1},{0,1} };//+{i,j}后分别是上下左右
        while (!rottenQueue.empty())
        {
            int n = rottenQueue.size();//当前队列中的腐烂橘子个数,处理完这n个橘子分钟数才+1
            bool rotten = false;
            for (int i = 0; i < n; i++) {
                //从队列头取出一个腐烂橘子
                auto rot = rottenQueue.front();
                for (auto side : around) {
                    int i = rot.first + side.first;
                    int j = rot.second + side.second;
                    if (i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1) {
                        grid[i][j] = 2;//这个橘子会腐烂
                        rottenQueue.push({ i,j });//将新腐烂的橘子加入队列
                        fresh--;//新鲜橘子减少一个
                        rotten = true;//当前橘子腐烂了周围的橘子
                    }
                }
                rottenQueue.pop();//已处理过的腐烂橘子无需再处理
            }
            if (rotten == true) {
                minute++;//分钟数+1
            }
        }
        return fresh == 0 ? minute : -1;
    }
};