腐烂的橘子
题目要求
在一个 m x n 的网格 grid 中，每个单元格可能包含以下三种值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
每过一分钟，任何与腐烂橘子相邻（上下左右四个方向）的新鲜橘子都会变腐烂。
任务是计算并返回使网格中所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。
解题思路
这个问题可以通过广度优先搜索（BFS）来解决。以下是解题步骤：
-
初始化队列和计数器：首先，遍历整个网格，将所有腐烂橘子的位置加入到队列中，并统计新鲜橘子的数量。
-
广度优先搜索：然后，进行 BFS，每次从队列中取出一个腐烂橘子的位置，查看其四周是否有新鲜橘子。如果有，则将新鲜橘子变为腐烂状态（即值从 1 变为 2），并将其位置加入队列中，同时新鲜橘子的数量减一。
-
时间计数：每完成一轮 BFS，表示过去了一分钟。在这一分钟内，所有与腐烂橘子相邻的新鲜橘子都会变腐烂。
-
检查新鲜橘子：当队列为空或新鲜橘子的数量变为 0 时，BFS 结束。如果还有新鲜橘子剩余，说明这些橘子无法被腐烂，返回
-1。否则，返回所用的分钟数。 -
边界条件处理：如果一开始就没有新鲜橘子，那么直接返回 0 分钟。
这个问题的关键在于如何有效地模拟橘子腐烂的过程，并且能够在所有橘子都腐烂或确定有橘子无法腐烂时停止搜索。通过 BFS，我们可以确保每一轮都是在模拟一分钟内腐烂的传播，这样可以准确计算出所需的最小分钟数。
Golang 版本
func orangesRotting(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
freshCount := 0
queue := make([][2]int, 0)
// 初始化队列，统计新鲜橘子数量
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == 2 {
queue = append(queue, [2]int{r, c})
} else if grid[r][c] == 1 {
freshCount++
}
}
}
// 如果没有新鲜橘子，直接返回0
if freshCount == 0 {
return 0
}
// 四个方向的移动向量
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
minutesPassed := 0
// 开始BFS
for len(queue) > 0 {
currentQueueSize := len(queue)
for i := 0; i < currentQueueSize; i++ {
orange := queue[0]
queue = queue[1:]
for _, d := range directions {
newRow, newCol := orange[0]+d[0], orange[1]+d[1]
// 检查新位置是否有效
if newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols {
if grid[newRow][newCol] == 1 {
grid[newRow][newCol] = 2
freshCount--
queue = append(queue, [2]int{newRow, newCol})
}
}
}
}
// 完成一轮BFS，时间增加
if len(queue) > 0 {
minutesPassed++
}
}
// 检查是否还有新鲜橘子
if freshCount == 0 {
return minutesPassed
}
return -1
}
这段代码定义了一个函数 orangesRotting，它接受一个二维整数数组 grid 作为输入，代表网格状态，并返回一个整数，表示使所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。代码使用广度优先搜索算法来模拟橘子腐烂的过程。
C++版本
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int freshCount = 0;
queue<pair<int, int>> q;
// 初始化队列，统计新鲜橘子数量
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == 2) {
q.push({r, c});
} else if (grid[r][c] == 1) {
freshCount++;
}
}
}
// 如果没有新鲜橘子，直接返回0
if (freshCount == 0) return 0;
// 四个方向的移动向量
vector<pair<int, int>> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int minutesPassed = 0;
// 开始BFS
while (!q.empty()) {
int currentQueueSize = q.size();
for (int i = 0; i < currentQueueSize; ++i) {
auto orange = q.front();
q.pop();
for (auto d : directions) {
int newRow = orange.first + d.first;
int newCol = orange.second + d.second;
// 检查新位置是否有效
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
if (grid[newRow][newCol] == 1) {
grid[newRow][newCol] = 2;
freshCount--;
q.push({newRow, newCol});
}
}
}
}
// 完成一轮BFS，时间增加
if (!q.empty()) {
minutesPassed++;
}
}
// 检查是否还有新鲜橘子
if (freshCount == 0) {
return minutesPassed;
}
return -1;
}
};
这段 C++代码定义了一个类 Solution，其中包含一个方法 orangesRotting，它接受一个二维整数数组 grid 作为输入，并返回一个整数，表示使所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。代码使用广度优先搜索算法来模拟橘子腐烂的过程。
Python 版本
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
fresh_count = 0
queue = deque()
# 初始化队列，统计新鲜橘子数量
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_count += 1
# 如果没有新鲜橘子，直接返回0
if fresh_count == 0:
return 0
minutes_passed = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 开始BFS
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
# 检查新位置是否有效
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh_count -= 1
queue.append((nr, nc))
if queue:
minutes_passed += 1
# 检查是否还有新鲜橘子
return minutes_passed if fresh_count == 0 else -1
这段 Python 代码定义了一个 Solution 类，其中包含一个方法 orangesRotting，它接受一个二维整数列表 grid 作为输入，并返回一个整数，表示使所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。代码使用广度优先搜索算法来模拟橘子腐烂的过程。
Java 版本
import java.util.*;
public class Solution {
public int orangesRotting(int[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0;
// 初始化队列，统计新鲜橘子数量
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) {
queue.offer(new int[]{r, c});
} else if (grid[r][c] == 1) {
freshCount++;
}
}
}
// 如果没有新鲜橘子，直接返回0
if (freshCount == 0) return 0;
int minutesPassed = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 开始BFS
while (!queue.isEmpty()) {
int currentQueueSize = queue.size();
for (int i = 0; i < currentQueueSize; i++) {
int[] orange = queue.poll();
for (int[] d : directions) {
int newRow = orange[0] + d[0];
int newCol = orange[1] + d[1];
// 检查新位置是否有效
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
if (grid[newRow][newCol] == 1) {
grid[newRow][newCol] = 2;
freshCount--;
queue.offer(new int[]{newRow, newCol});
}
}
}
}
if (!queue.isEmpty()) {
minutesPassed++;
}
}
// 检查是否还有新鲜橘子
return freshCount == 0 ? minutesPassed : -1;
}
}
这段 Java 代码定义了一个 Solution 类，其中包含一个方法 orangesRotting，它接受一个二维整数数组 grid 作为输入，并返回一个整数，表示使所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。代码使用广度优先搜索算法来模拟橘子腐烂的过程。
Rust 版本
#![allow(unused)] fn main() { use std::collections::VecDeque; pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 { let rows = grid.len(); let cols = grid[0].len(); let mut queue: VecDeque<(usize, usize)> = VecDeque::new(); let mut fresh_count = 0; // 初始化队列，统计新鲜橘子数量 for r in 0..rows { for c in 0..cols { match grid[r][c] { 2 => queue.push_back((r, c)), 1 => fresh_count += 1, _ => (), } } } // 如果没有新鲜橘子，直接返回0 if fresh_count == 0 { return 0; } let mut minutes_passed = 0; let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]; // 开始BFS while let Some((r, c)) = queue.pop_front() { let mut added = false; for d in directions.iter() { let (dr, dc) = *d; let (new_r, new_c) = (r as i32 + dr, c as i32 + dc); if new_r >= 0 && new_r < rows as i32 && new_c >= 0 && new_c < cols as i32 { let (new_r, new_c) = (new_r as usize, new_c as usize); if grid[new_r][new_c] == 1 { grid[new_r][new_c] = 2; fresh_count -= 1; queue.push_back((new_r, new_c)); added = true; } } } if added { minutes_passed += 1; } } // 检查是否还有新鲜橘子 if fresh_count == 0 { minutes_passed } else { -1 } } }
这段 Rust 代码定义了一个函数 oranges_rotting，它接受一个二维向量 grid 作为输入，并返回一个整数，表示使所有新鲜橘子变腐烂所需的最小分钟数。如果存在无法被腐烂的新鲜橘子，则返回 -1。代码使用广度优先搜索算法来模拟橘子腐烂的过程。注意，Rust 中的索引必须是 usize 类型，因此在处理索引时需要进行类型转换。
总结
上面的解法采用了广度优先搜索（BFS）算法来解决“腐烂的橘子”问题。这个问题可以被看作是在一个二维网格上的感染扩散模型，其中橘子可以处于新鲜状态（1）或腐烂状态（2），空单元格（0）不参与感染过程。
解法的关键步骤如下：
-
初始化队列和统计新鲜橘子： 遍历整个网格，将所有腐烂的橘子的位置加入队列，并统计新鲜橘子的数量。
-
特殊情况处理： 如果没有新鲜橘子，直接返回 0，因为不需要时间来腐烂。
-
广度优先搜索（BFS）： 使用队列来进行 BFS，每次从队列中取出一个腐烂的橘子的位置，然后查看其上下左右的邻居。如果邻居是新鲜橘子（1），则将其腐烂（变为 2），并将其位置加入队列，同时减少新鲜橘子的数量。
-
时间计数： 每完成一轮队列中的橘子处理，时间增加 1。这模拟了每分钟腐烂橘子影响其邻居的过程。
-
检查是否还有新鲜橘子： 完成 BFS 后，如果还有新鲜橘子，说明它们无法被腐烂的橘子感染到，返回-1。否则，返回所需的分钟数。
这个解法的时间复杂度通常是 O(mn)，其中 m 是网格的行数，n 是网格的列数，因为每个单元格最多只会被访问一次。空间复杂度也是 O(mn)，主要是因为在最坏的情况下，可能需要存储整个网格中所有的橘子位置。