腐烂的橘子

题目分析

题目描述的是一个典型的 多源广度优先搜索（BFS） 问题。在一个 m × n 的网格中，腐烂的橘子会以 四个方向（上、下、左、右）向外扩散，每经过一分钟，相邻的新鲜橘子（值 1）就会变成腐烂的橘子（值 2）。我们的目标是求出所有新鲜橘子变成腐烂橘子的最短时间。如果有新鲜橘子无法被腐蚀，则返回 -1。

解题思路

1. 数据预处理：
   • 遍历整个 grid，记录所有腐烂橘子的位置，将其存入 队列 queue 中（用于 BFS）。
   • 统计新鲜橘子的数量 fresh_count，如果 fresh_count == 0，则立即返回 0。

Leetcode 52.腐烂的橘子-原题链接

题目内容

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

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

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

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

输入描述

• 第一行两个整数$n,m$。
• 接下来有$n$行，每行$m$列，表示网格，每行里的数字以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

3 3
2 1 1
1 1 0
0 1 1

输出

4

说明

样例2

输入

3 3
2 1 1
0 1 1
1 0 1

输出

-1

说明

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

样例3

输入

1 2
0 2

输出

0

说明

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

提示

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