腐烂的橘子

难度：⭐⭐⭐ 面试高频

考点

• 多源 BFS
• 层序遍历计时
• 字节面试高频题

题目描述

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

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

每分钟，腐烂橘子的四方向相邻新鲜橘子都会变腐烂。返回直到没有新鲜橘子为止所经过的最小分钟数。如果不可能，返回 -1。

函数签名

func orangesRotting(grid [][]int) int

示例

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

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1（左下角永远无法被感染）

输入：grid = [[0,2]]
输出：0（没有新鲜橘子）

要求

1. 时间复杂度 O(m*n)
2. 使用多源 BFS

提示

• 初始时所有腐烂橘子同时入队（多源 BFS）
• 层序遍历：每层代表一分钟
• 统计新鲜橘子数 fresh，每感染一个 fresh--
• BFS 结束后 fresh > 0 → 返回 -1
• 注意初始 fresh=0 时直接返回 0

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func orangesRotting(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	queue := make([][2]int, 0)
	fresh := 0

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, [2]int{i, j})
			} else if grid[i][j] == 1 {
				fresh++
			}
		}
	}

	if fresh == 0 {
		return 0
	}

	dirs := [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	minutes := 0

	for len(queue) > 0 {
		size := len(queue)
		for k := 0; k < size; k++ {
			cur := queue[0]
			queue = queue[1:]
			for _, d := range dirs {
				nx, ny := cur[0]+d[0], cur[1]+d[1]
				if nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1 {
					grid[nx][ny] = 2
					fresh--
					queue = append(queue, [2]int{nx, ny})
				}
			}
		}
		minutes++
	}

	if fresh > 0 {
		return -1
	}
	if minutes == 0 {
		return 0
	}
	return minutes - 1
}