leetcode994:腐烂的橘子

题目链接

leetcode

题目描述

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

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

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1

C++ 代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

/*
每分钟每个腐烂的橘子会使上下左右相邻的新鲜橘子腐烂,
这是一个模拟广度优先搜索的过程。

广度优先搜索,从起点出发,每次都尝试访问同一层的节点。
如果同一层都访问完了,再访问下一层。
最后找到的路径,就是从起点开始的最短合法路径。

时间复杂度:O(mn)
其中 m, n 分别为 grid 的行数与列数。
空间复杂度:O(mn)
数组记录每个新鲜橘子被腐烂的最短时间,空间 O(mn)。
队列中存放的状态最多不会超过 mn 个,空间 O(mn)。
*/
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
memset(badTime, -1, sizeof(badTime));
queue<pair<int, int>> badOranges;
int count = 0; // 记录新鲜的橘子数量

// 遍历二维数组:腐烂的橘子存入队列、设置腐烂的时间,新鲜的橘子统计数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
badOranges.emplace(i, j);
badTime[i][j] = 0;
} else if (grid[i][j] == 1) {
count++;
}
}
}

int res = 0;
// BFS 循环
while (!badOranges.empty()) {
auto badOrange = badOranges.front(); badOranges.pop();
int row = badOrange.first, col = badOrange.second;

// 根据方向开始遍历
for (int i = 0; i < 4; i++) {
int x = row + dx[i], y = col + dy[i];

// 更新新鲜橘子的数量,以及腐烂的时间
if (x >= 0 && x < m && y >= 0 && y < n && badTime[x][y] == -1 && grid[x][y] != 0) {
badTime[x][y] = badTime[row][col] + 1;
badOranges.emplace(x, y);

if (grid[x][y] == 1) {
grid[x][y] = 2;
count--;
res = badTime[x][y];
if (count == 0) {
break;
}
}
}
}
}

return count == 0 ? res : -1;
}

private:
static const int N = 10;
int badTime[N][N]; // 记录橘子全部腐烂需要的时间
int dx[4] = { -1, 0, 1, 0 }; // 横坐标,方向:上右下左
int dy[4] = { 0, 1, 0, -1 }; // 纵坐标,方向:上右下左
};

// 辅助函数:打印二维数组
void printArray(const vector<vector<int>>& nums) {
cout << "[";
for (size_t i = 0; i < nums.size(); i++) {
cout << "[";
for (size_t j = 0; j < nums[i].size(); j++) {
cout << nums[i][j];
if (j != nums[i].size() - 1) cout << ",";
}
cout << "]";
if (i != nums.size() - 1) cout << ",";
}
cout << "]" << endl;
}

int main() {
Solution solution;
vector<vector<vector<int>>> grid_cases = {
{{2,1,1},{1,1,0},{0,1,1}},
{{2,1,1},{0,1,1},{1,0,1}},
{{0,2}}
};

for (int i = 0; i < grid_cases.size(); i++) {
auto& grid = grid_cases[i];
cout << "Input: grid = ";
printArray(grid);

int result = solution.orangesRotting(grid);
cout << "Output: " << result << endl;
}

return 0;
}

leetcode994:腐烂的橘子
https://lcf163.github.io/2024/05/26/leetcode994:腐烂的橘子/
作者
乘风的小站
发布于
2024年5月26日
许可协议