文章目录
腐烂的橘子
题目描述
思路详解
观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。
假设这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂，而这个腐烂橘子刚开始在的时间是 −1 ，那么按照广度优先搜索的算法，下一分钟也就是第 0 分钟的时候，这个腐烂橘子会把它们都变成腐烂橘子，然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，最后每个新鲜橘子被腐烂的最短时间dis[x][y] 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。
为了确认是否所有新鲜橘子都被腐烂，可以记录一个变量 cnt 表示当前网格中的新鲜橘子数，广度优先搜索的时候如果有新鲜橘子被腐烂，则 cnt-=1 ，最后搜索结束时如果 cnt 大于 0 ，说明有新鲜橘子没被腐烂，返回 −1 ，否则返回所有新鲜橘子被腐烂的时间的最大值即可，也可以在广度优先搜索的过程中把已腐烂的新鲜橘子的值由 1 改为 2，最后看网格中是否由值为 1 即新鲜的橘子即可。
代码与结果
class Solution { int[] dr = new int[]{-1, 0, 1, 0}; int[] dc = new int[]{0, -1, 0, 1}; public int orangesRotting(int[][] grid) { int R = grid.length, C = grid[0].length; Queue<Integer> queue = new ArrayDeque<Integer>(); Map<Integer, Integer> depth = new HashMap<Integer, Integer>(); for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { if (grid[r][c] == 2) { int code = r * C + c; queue.add(code); depth.put(code, 0); } } } int ans = 0; while (!queue.isEmpty()) { int code = queue.remove(); int r = code / C, c = code % C; for (int k = 0; k < 4; ++k) { int nr = r + dr[k]; int nc = c + dc[k]; if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) { grid[nr][nc] = 2; int ncode = nr * C + nc; queue.add(ncode); depth.put(ncode, depth.get(code) + 1); ans = depth.get(ncode); } } } for (int[] row: grid) { for (int v: row) { if (v == 1) { return -1; } } } return ans; } }
✨总结
今天有些事情发生，所以算法今天只刷了一题。参考了官方解答，小伙伴们一起练一练吧。
