当前位置：首页 > article >正文

如何在网格中模拟腐烂扩散：如何使用广度优先搜索（BFS）解题

article 2024/10/3 22:38:24

问题描述

你需要在一个二维的网格中处理橘子的腐烂扩散过程，网格中的每个单元格可以有三种状态：

0：表示空格，没有橘子。
1：表示一个新鲜的橘子。
2：表示一个腐烂的橘子，它可以在 1 分钟内让上下左右四个方向的新鲜橘子也变腐烂。

你的任务是：计算让所有橘子腐烂所需的最少时间。如果存在无法腐烂的橘子，返回 -1。

994. 腐烂的橘子 - 力扣（LeetCode）

这个问题可以看作一个 广度优先搜索（BFS） 问题，类似于在网格中扩散的过程。每个腐烂的橘子会以每分钟的时间向四周扩散，找到所有橘子完全腐烂所需要的最短时间。如果存在无法腐烂的橘子，则返回 -1。

我们可以借助 BFS 的特性，一步步地扩散腐烂橘子，并记录时间。

如何理解最短腐烂时间？

最短腐烂时间的概念类似于在广度优先搜索中寻找从一个起点扩展到所有节点的最短路径。换句话说，每个腐烂的橘子以相同的速度向四周扩散，我们要找到让所有新鲜橘子完全腐烂所需的最少分钟数。

BFS 的优势

层次遍历：BFS 是按层次遍历的，也就是每次扩散到下一层需要的步数（分钟数）是相同的。
最短路径保证：BFS 会确保我们从某个腐烂橘子第一次到达某个新鲜橘子的时间最短。因为每次扩展的步数都是均匀的，先腐烂的橘子会先腐蚀周围的新鲜橘子。

解题思路：

数据结构选择：
- 使用队列（queue）来进行 BFS，因为我们需要逐层处理腐烂橘子的扩散。
- 每次从队列中取出一个腐烂橘子，并向它的上下左右四个方向扩展。如果碰到新鲜橘子，则将其变为腐烂橘子，并加入队列。
初始化队列：
- 首先遍历整个网格，将所有腐烂的橘子（值为 2）的坐标加入队列，作为 BFS 的起点。
- 同时统计新鲜橘子（值为 1）的数量。如果一开始没有新鲜橘子，则直接返回 0。
BFS 扩展：
- 从队列中取出腐烂橘子，向四个方向扩展，感染新鲜橘子。每次感染新鲜橘子，腐烂时间加 1，并将新鲜橘子加入队列。
- 记录经过的时间，直到没有新鲜橘子可以腐烂。
处理无法腐烂的情况：
- 如果 BFS 结束时，仍然有新鲜橘子（即队列处理完毕但仍有 1 存在），返回 -1。
- 如果所有新鲜橘子都腐烂了，返回腐烂所需要的最短时间。
处理 -1 的特殊情况：
- 如果有橘子永远无法被腐烂，例如它们周围被 0 包围，最终会返回 -1。

代码实现

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 队列用于存放腐烂橘子的坐标
        queue<pair<int, int>> q;
        int fresh_count = 0;  // 新鲜橘子的数量
        
        // 遍历整个网格，初始化队列并统计新鲜橘子的数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});  // 将腐烂的橘子放入队列
                } else if (grid[i][j] == 1) {
                    fresh_count++;  // 统计新鲜橘子的数量
                }
            }
        }
        
        // 如果一开始就没有新鲜橘子，直接返回 0
        if (fresh_count == 0) return 0;
        
        // 方向数组，用于向四个方向扩展：上、下、左、右
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        int minutes = 0;  // 记录经过的分钟数
        
        // 开始 BFS
        while (!q.empty()) {
            int size = q.size();  // 当前层的腐烂橘子数量
            bool has_rotted = false;  // 记录是否有新橘子腐烂
            
            for (int i = 0; i < size; i++) {
                auto [x, y] = q.front();
                q.pop();
                
                // 遍历四个方向
                for (auto [dx, dy] : directions) {
                    int newX = x + dx;
                    int newY = y + dy;
                    
                    // 检查新的坐标是否有效并且是新鲜橘子
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
                        // 新鲜橘子腐烂
                        grid[newX][newY] = 2;
                        fresh_count--;  // 新鲜橘子数量减少
                        q.push({newX, newY});  // 将新腐烂的橘子加入队列
                        has_rotted = true;  // 标记当前层有橘子腐烂
                    }
                }
            }
            
            // 只有当当前层有新鲜橘子腐烂时，才增加时间
            if (has_rotted) minutes++;
        }
        
        // 如果最终还有新鲜橘子没有腐烂，返回 -1
        return fresh_count == 0 ? minutes : -1;
    }
};

代码逻辑详细解释

初始化队列与统计新鲜橘子：
- 遍历整个网格，遇到腐烂橘子（值为 2）时，将其坐标存入队列。
- 同时统计新鲜橘子（值为 1）的数量。如果没有新鲜橘子，直接返回 0，因为不需要腐烂操作。
BFS 扩展腐烂过程：
- 队列中每个元素表示一个腐烂的橘子。我们从队列中取出腐烂橘子，检查其四个方向（上、下、左、右）是否有新鲜橘子。
- 如果找到新鲜橘子，就将其标记为腐烂并加入队列。同时将新鲜橘子的数量减少。
时间记录：
- 每处理完当前层的腐烂橘子，若有新鲜橘子被腐烂，才将时间 minutes 增加。
- 如果在某一层的所有腐烂橘子都不能腐烂周围的橘子，那么本层结束后不增加时间。
处理无法腐烂的橘子：
- BFS 结束后，若还有新鲜橘子（fresh_count > 0），说明有橘子无法被腐烂。此时返回 -1。
返回结果：
- 如果所有橘子都腐烂了，则返回腐烂的总时间。否则返回 -1。

示例讲解

示例 1：

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]

在这里插入图片描述

过程：

初始腐烂橘子坐标为 (0,0)。
第 1 分钟：腐烂橘子 (0,0) 腐烂周围的橘子 (0,1) 和 (1,0)。
- 队列状态：[(0,1), (1,0)]
- 剩余新鲜橘子数量：4
第 2 分钟：橘子 (0,1) 和 (1,0) 分别腐烂其相邻的橘子 (0,2) 和 (1,1)。
- 队列状态：[(0,2), (1,1)]
- 剩余新鲜橘子数量：2
第 3 分钟：橘子 (0,2) 和 (1,1) 分别腐烂其相邻的橘子 (1,2) 和 (2,1)。
- 队列状态：[(1,2), (2,1)]
- 剩余新鲜橘子数量：1
第 4 分钟：橘子 (1,2) 和 (2,1) 腐烂最后一个新鲜橘子 (2,2)。
- 队列状态：[(2,2)]
- 剩余新鲜橘子数量：0
所有橘子腐烂，总共耗时 4 分钟。

输出：4

示例 2：

grid = [[2,1,1],
        [0,1,1],
        [1,0,1]]

过程：

第一轮 BFS：
- 从队列中取出 (0,0)，它周围的四个方向分别是：
  1. (1,0)，这是 0，无法通过墙传播。
  2. (-1,0)，超出边界。
  3. (0,1)，这是新鲜橘子 1，变为腐烂橘子，并加入队列。
  4. (0,-1)，超出边界。

队列状态：[(0,1)]，剩余新鲜橘子：5，时间增加 minutes++（时间变为 1）

第二轮 BFS：
- 从队列中取出 (0,1)，它周围的四个方向分别是：
  1. (1,1)，新鲜橘子，变为腐烂，加入队列。
  2. (-1,1)，超出边界。
  3. (0,2)，新鲜橘子，变为腐烂，加入队列。
  4. (0,0)，已经是腐烂橘子，跳过。

队列状态：[(1,1), (0,2)]，剩余新鲜橘子：3，时间增加 minutes++（时间变为 2）

第三轮 BFS：
- 从队列中取出 (1,1) 和 (0,2)，它们周围分别是：
  1. (2,1)，是 0，不能腐烂。
  2. (1,2)，新鲜橘子，变为腐烂，加入队列。
  3. (1,0)，是 0，无法腐烂。

队列状态：[(1,2)]，剩余新鲜橘子：2，时间增加 minutes++（时间变为 3）

第四轮 BFS：
- 从队列中取出 (1,2)，它周围的四个方向分别是：
  1. (2,2)，新鲜橘子，变为腐烂，加入队列。
  2. (0,2)，已经腐烂。
  3. (1,1)，已经腐烂。
  4. (1,3)，超出边界。

队列状态：[(2,2)]，剩余新鲜橘子：1，时间增加 minutes++（时间变为 4）

取出 [(2,2)]：
- (2,2) 是最后一个腐烂橘子。
- 它的四个方向的检查：
  1. (1,2) 已经腐烂，跳过。
  2. (2,1) 是墙壁 0，无法腐烂。
  3. (3,2) 超出边界。
  4. (2,3) 超出边界。
- 这时候队列 q 变为空。
跳出 BFS 循环：
- 由于队列为空，while (!q.empty()) 条件不再成立，循环结束。
判断是否有剩余新鲜橘子：
- 循环结束后，代码会检查是否仍有未腐烂的新鲜橘子。
- 此时，grid[2][0] 橘子由于被 grid[1][0] 的墙壁阻隔，它从未进入过 BFS 队列，也没有腐烂。
- 因此，freshOranges 为1，仍然大于 0，即还有剩余的新鲜橘子，无法被腐烂。
- 代码中执行：
```
return freshOranges == 0 ? minutes : -1;
```
- 由于 freshOranges > 0，返回 -1。