LeetCode994腐烂的橘子
题目描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
解析
对于每一个腐烂的橘子，每次都使其周围的橘子变成腐烂的橘子，就是同时又多个起点的BFS算法，有点类似洪泛这种。
public int orangesRotting(int[][] grid) {Queue<int[]> queue = new ArrayDeque<>();int freshOranges = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] == 1) {freshOranges++;}}}if (freshOranges == 0) return 0;int minutes = 0;int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (!queue.isEmpty()) {int currentLevelSize = queue.size();for (int i = 0; i < currentLevelSize; i++) {int[] cur = queue.poll();for (int[] direction : directions) {int newX = cur[0] + direction[0];int newY = cur[1] + direction[1];if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1) {grid[newX][newY] = 2; // Mark as rottenqueue.offer(new int[]{newX, newY});freshOranges--;}}}minutes++; // Completed one minute}return freshOranges == 0 ? minutes - 1 : -1; // Adjust minutes as the last minute may not count
}
