面试题6 -- 腐烂的苹果（多源DFS）

腐烂的苹果（多源DFS）

题目链接： 腐烂的苹果_多源DFS

描述

给定一个 n×m 的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围

1≤n,m≤1000 ，网格中的值满足 0≤val≤2

解题思路

这个问题可以通过广度优先搜索（BFS）来解决，因为我们需要以最短的时间传播腐烂的苹果。我们可以将每个腐烂的苹果看作是一个源点，然后从这些源点同时开始传播。

1. 初始化队列：首先，我们将所有初始状态为腐烂的苹果的位置加入到一个队列中，因为它们是传播腐烂的源头。
2. 广度优先搜索：然后，我们进行广度优先搜索。对于队列中的每个苹果，我们检查它的四个邻居（上、下、左、右）。如果邻居是一个完好的苹果（值为1），我们就将它变为腐烂的苹果，并将其位置加入队列中，以便在下一分钟继续传播。（注意避免一个位置被重复加入队列）
3. **记录时间：**我们需要记录传播的层数，即分钟数。每次从队列中取出元素时，层数加1。
4. **检查完好的苹果：**当队列为空时，我们检查网格中是否还有完好的苹果。如果有，说明它们永远不会腐烂，我们返回-1。否则，我们返回传播所需的分钟数。

代码拟写及相关注意点

注意点：

• 为了便于我们管理整个矩阵中的所有点，由于每个点的横纵坐标唯一性，使用pair对坐标实现统一管理
• 其次，为了避免判断周围坐标点代码冗余，给出向量数组（分别对应上右下左<顺时针>），通过统一处理就可以只通过遍历向量数组时下标的轮转来得到指定点上下左右的点横纵坐标
• 同时注意同一点不能重复入队列以及每次取front()都要对应pop()移除对头，否则会导致 内存超限 控制出队列的循环永无止境，从而程序超时判否

示例代码：

class Solution {
public:
    using pii = pair<int, int>;
    // 顺时针给出向量数组
    int x_arr[4] = {0, 1, 0, -1};
    int y_arr[4] = {1, 0, -1, 0};
    bool visit[1001][1001] = {false};
    int rotApple(vector<vector<int> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        queue<pii> q;

        // 先把坏苹果移入队列
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 2) { q.push({i, j}); }
            }
        }

        int cnt = 0;    // 记录层数（分钟数）
        while(!q.empty())   // 遍历所有节点
        {
            int size = q.size();
            cnt++;
            while(size--)   // 逐层遍历
            {
                auto [x, y] = q.front();
                // 将该层的每个节点最短路展开，符合条件的节点push进队列
                for(int i = 0; i < 4; i++)
                {
                    int tmp_x = x + x_arr[i];
                    int tmp_y = y + y_arr[i];
                    if(tmp_x >= 0 && tmp_x < m && tmp_y >= 0 && tmp_y < n
                        && grid[tmp_x][tmp_y] == 1 && !visit[tmp_x][tmp_y])
                    {
                        q.push({tmp_x, tmp_y});
                        visit[tmp_x][tmp_y] = true;
                    }
                }
                q.pop();
            }
        }

        // 检查是否有苹果未被感染
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == 1 && !visit[i][j]) { return -1; }
            }
        }

        return cnt - 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

提交截图：

总结

​ 问题的关键是理解如何使用BFS来模拟腐烂的传播过程。我们需要维护一个队列来存储每一分钟需要传播的苹果位置，并且需要一个二维数组来标记已经访问过的位置，以避免重复处理。通过逐层传播，我们可以确保每个苹果都是以最短的时间腐烂。最后，我们通过检查网格中是否还有完好的苹果来确定所有苹果是否都已腐烂。如果所有苹果都已腐烂，我们返回总的分钟数；如果有苹果永远不会腐烂，我们返回-1。

​ 这个解法的时间复杂度是O(n*m)，其中n和m分别是网格的行数和列数。