994. 腐烂的橘子

🟠   🔖  广度优先搜索 数组 矩阵  🔗 力扣 LeetCode

题目

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

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

Output: 4

Example 2:

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

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

题目大意

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

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

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例 1：


输入： grid = [[2,1,1],[1,1,0],[0,1,1]]

输出： 4

示例 2：

输入： grid = [[2,1,1],[0,1,1],[1,0,1]]

输出： -1

解释： 左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入： grid = [[0,2]]

输出： 0

解释： 因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

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

解题思路

可以使用广度优先搜索 (BFS) 来解决这个问题，BFS 的特点是层次遍历，非常适合模拟这种扩散问题。

1. 初始化队列

首先需要找到所有的腐烂橘子，并将它们的坐标存储在队列中。同时记录网格中新鲜橘子的数量 freshCount。

2. 扩散腐烂橘子

每分钟从队列中取出当前腐烂橘子的坐标，并将其扩散到相邻的四个方向。如果相邻的橘子是新鲜的，腐烂橘子会让它变成腐烂的，并将其加入队列中，同时减少新鲜橘子的计数。

3. 检查是否成功腐烂所有橘子

每次扩散完之后，检查是否还有新鲜橘子存在。如果所有新鲜橘子都被腐烂了，返回扩散所需的分钟数。如果有新鲜橘子无法被腐烂（即它们周围没有腐烂橘子），返回 -1。

复杂度分析

• 时间复杂度: O(m * n)，其中 m 和 n 分别是二维矩阵的长和宽，需要遍历整个矩阵以标记所有腐烂的橘子。
• 空间复杂度: O(m * n)，最多需要在队列中存储 m * n 个橘子的坐标。

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
	const m = grid.length,
		n = grid[0].length;

	let queue = [],
		freshCount = 0;

	// 遍历矩阵，找到所有坏橘子，并计算所有新鲜橘子的数量
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] == 1) {
				freshCount++;
			} else if (grid[i][j] == 2) {
				queue.push([i, j]);
			}
		}
	}
	// 如果没有新鲜橘子，返回 0
	if (freshCount == 0) return 0;

	let minutes = 0;
	// 上、下、左、右
	const dirc = [
		[-1, 0],
		[1, 0],
		[0, -1],
		[0, 1]
	];

	// BFS 遍历坏橘子的邻居
	while (queue.length) {
		let len = queue.length,
			findFresh = false;
		for (let i = 0; i < len; i++) {
			const [x, y] = queue.shift();
			for (let [dx, dy] of dirc) {
				const newX = x + dx;
				const newY = y + dy;

				if (
					newX >= 0 &&
					newX < m &&
					newY >= 0 &&
					newY < n &&
					grid[newX][newY] == 1
				) {
					// 将新鲜橘子变坏
					grid[newX][newY] = 2;
					freshCount--;
					queue.push([newX, newY]);
					findFresh = true;
				}
			}
		}
		// 如果有新鲜橘子变坏，minutes 加一
		if (findFresh) {
			minutes++;
		}
	}

	// 如果依然有新鲜橘子，返回 -1
	return freshCount == 0 ? minutes : -1;
};

相关题目

题号	标题	题解	标签	难度
286	墙与门 🔒		广度优先搜索 数组 矩阵
419	棋盘上的战舰		深度优先搜索 数组 矩阵
2101	引爆最多的炸弹		深度优先搜索 广度优先搜索 图 3+
2258	逃离火灾		广度优先搜索 数组 二分查找 1+