题目描述给定一个m x n的网格grid每个单元格可能有三种值0表示空单元格。1表示新鲜橘子。2表示腐烂的橘子。每分钟腐烂的橘子会让上下左右四个方向相邻的新鲜橘子腐烂。要求返回直到没有新鲜橘子为止所需的最小分钟数。如果存在新鲜橘子永远无法腐烂返回-1。初始思路一开始容易想到 DFS从每个腐烂橘子出发去感染周围的新鲜橘子。但这个思路有一个关键问题题目里的腐烂过程是“每分钟同时扩散”而普通 DFS 更像是一条路径一直往深处走。DFS 不能自然表达“第 1 分钟腐烂哪些橘子第 2 分钟腐烂哪些橘子”。比如最开始写成“遇到腐烂橘子就把周围一圈新鲜橘子变腐烂”这其实只模拟了 1 分钟并没有继续分层扩散也没有正确统计答案。所以这题更适合使用多源 BFS。解题思路把网格看成一张图每个橘子格子可以看作一个节点。上下左右相邻表示节点之间有边。所有初始腐烂橘子2都是 BFS 的起点。因为一开始可能有多个腐烂橘子而且它们会同时向外扩散所以不能只从一个点开始 BFS而是要把所有初始腐烂橘子一起加入队列。这就是多源 BFS。具体流程遍历整个grid。遇到腐烂橘子2加入队列。遇到新鲜橘子1统计数量fresh。BFS 每次处理当前队列中的size个橘子。这一批橘子代表同一分钟内会继续扩散的腐烂橘子。如果感染到新鲜橘子就把它改成2同时fresh--再加入队列。BFS 结束后如果fresh 0说明所有新鲜橘子都腐烂了否则返回-1。为什么要按层 BFSBFS 中的“一层”正好对应题目中的“一分钟”。例如2 1 1 1 1 0 0 1 1第 1 分钟初始腐烂橘子影响周围2 2 1 2 1 0 0 1 1第 2 分钟新腐烂的橘子继续扩散2 2 2 2 2 0 0 1 1所以代码里需要先记录当前队列大小int size queue.size();然后只处理这size个元素。新加入队列的橘子不能在同一分钟继续扩散而是留到下一轮处理。易错点1. Java 数组入队写法Java 中不能这样写queue.add({i, j});应该写成queue.add(new int[]{i, j});因为{i, j}只能在数组初始化语境中使用不能单独作为一个对象传入方法。2. BFS 循环条件如果写成while (!queue.isEmpty()) { minutes; }答案可能会多 1。原因是最后一批刚刚腐烂的橘子还会留在队列里再被处理一轮。但这一轮已经没有新的新鲜橘子可以腐烂了不应该再增加分钟数。更稳妥的写法是while (!queue.isEmpty() fresh 0) { minutes; }只有在还存在新鲜橘子时继续按分钟扩散。3. 最后要判断是否还有新鲜橘子BFS 结束不代表所有新鲜橘子都腐烂了。如果某些新鲜橘子被空格隔开永远无法被腐烂橘子感染就需要返回-1。所以最后要根据fresh判断return fresh 0 ? minutes : -1;代码实现class Solution { int[][] D { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; int m; int n; public int orangesRotting(int[][] grid) { m grid.length; n grid[0].length; Dequeint[] queue new ArrayDeque(); int fresh 0; int minutes 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { queue.add(new int[]{i, j}); } else if (grid[i][j] 1) { fresh; } } } while (!queue.isEmpty() fresh 0) { int size queue.size(); minutes; for (int i 0; i size; i) { int[] cur queue.poll(); for (int[] d : D) { int x cur[0] d[0]; int y cur[1] d[1]; if (x 0 x m y 0 y n grid[x][y] 1) { grid[x][y] 2; fresh--; queue.add(new int[]{x, y}); } } } } return fresh 0 ? minutes : -1; } }复杂度分析时间复杂度O(m * n)。每个格子最多入队一次最多被检查一次。空间复杂度O(m * n)。最坏情况下队列中可能存放大量腐烂橘子。复盘这题的关键不是“会不会遍历四个方向”而是能不能看出它是一个按时间分层扩散的问题。当题目出现“每分钟”“同时扩散”“最短时间”这类描述时要优先考虑 BFS。并且如果一开始有多个源头比如多个腐烂橘子就要想到多源 BFS。下次写类似题时可以先检查三点是否把所有起点都加入队列而不是只从一个点开始。是否用size queue.size()区分每一分钟。是否用剩余数量fresh判断答案和-1。
题目描述给定一个m x n的网格grid每个单元格可能有三种值0表示空单元格。1表示新鲜橘子。2表示腐烂的橘子。每分钟腐烂的橘子会让上下左右四个方向相邻的新鲜橘子腐烂。要求返回直到没有新鲜橘子为止所需的最小分钟数。如果存在新鲜橘子永远无法腐烂返回-1。初始思路一开始容易想到 DFS从每个腐烂橘子出发去感染周围的新鲜橘子。但这个思路有一个关键问题题目里的腐烂过程是“每分钟同时扩散”而普通 DFS 更像是一条路径一直往深处走。DFS 不能自然表达“第 1 分钟腐烂哪些橘子第 2 分钟腐烂哪些橘子”。比如最开始写成“遇到腐烂橘子就把周围一圈新鲜橘子变腐烂”这其实只模拟了 1 分钟并没有继续分层扩散也没有正确统计答案。所以这题更适合使用多源 BFS。解题思路把网格看成一张图每个橘子格子可以看作一个节点。上下左右相邻表示节点之间有边。所有初始腐烂橘子2都是 BFS 的起点。因为一开始可能有多个腐烂橘子而且它们会同时向外扩散所以不能只从一个点开始 BFS而是要把所有初始腐烂橘子一起加入队列。这就是多源 BFS。具体流程遍历整个grid。遇到腐烂橘子2加入队列。遇到新鲜橘子1统计数量fresh。BFS 每次处理当前队列中的size个橘子。这一批橘子代表同一分钟内会继续扩散的腐烂橘子。如果感染到新鲜橘子就把它改成2同时fresh--再加入队列。BFS 结束后如果fresh 0说明所有新鲜橘子都腐烂了否则返回-1。为什么要按层 BFSBFS 中的“一层”正好对应题目中的“一分钟”。例如2 1 1 1 1 0 0 1 1第 1 分钟初始腐烂橘子影响周围2 2 1 2 1 0 0 1 1第 2 分钟新腐烂的橘子继续扩散2 2 2 2 2 0 0 1 1所以代码里需要先记录当前队列大小int size queue.size();然后只处理这size个元素。新加入队列的橘子不能在同一分钟继续扩散而是留到下一轮处理。易错点1. Java 数组入队写法Java 中不能这样写queue.add({i, j});应该写成queue.add(new int[]{i, j});因为{i, j}只能在数组初始化语境中使用不能单独作为一个对象传入方法。2. BFS 循环条件如果写成while (!queue.isEmpty()) { minutes; }答案可能会多 1。原因是最后一批刚刚腐烂的橘子还会留在队列里再被处理一轮。但这一轮已经没有新的新鲜橘子可以腐烂了不应该再增加分钟数。更稳妥的写法是while (!queue.isEmpty() fresh 0) { minutes; }只有在还存在新鲜橘子时继续按分钟扩散。3. 最后要判断是否还有新鲜橘子BFS 结束不代表所有新鲜橘子都腐烂了。如果某些新鲜橘子被空格隔开永远无法被腐烂橘子感染就需要返回-1。所以最后要根据fresh判断return fresh 0 ? minutes : -1;代码实现class Solution { int[][] D { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; int m; int n; public int orangesRotting(int[][] grid) { m grid.length; n grid[0].length; Dequeint[] queue new ArrayDeque(); int fresh 0; int minutes 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) { queue.add(new int[]{i, j}); } else if (grid[i][j] 1) { fresh; } } } while (!queue.isEmpty() fresh 0) { int size queue.size(); minutes; for (int i 0; i size; i) { int[] cur queue.poll(); for (int[] d : D) { int x cur[0] d[0]; int y cur[1] d[1]; if (x 0 x m y 0 y n grid[x][y] 1) { grid[x][y] 2; fresh--; queue.add(new int[]{x, y}); } } } } return fresh 0 ? minutes : -1; } }复杂度分析时间复杂度O(m * n)。每个格子最多入队一次最多被检查一次。空间复杂度O(m * n)。最坏情况下队列中可能存放大量腐烂橘子。复盘这题的关键不是“会不会遍历四个方向”而是能不能看出它是一个按时间分层扩散的问题。当题目出现“每分钟”“同时扩散”“最短时间”这类描述时要优先考虑 BFS。并且如果一开始有多个源头比如多个腐烂橘子就要想到多源 BFS。下次写类似题时可以先检查三点是否把所有起点都加入队列而不是只从一个点开始。是否用size queue.size()区分每一分钟。是否用剩余数量fresh判断答案和-1。
