网站正在维护中,免费手机端网站模板下载工具,百度推广后台登录,汕头百度网络推广文章目录 题目方法一#xff1a;bfs层序遍历 题目 该题值推荐用bfs#xff0c;因为是一层一层的感染#xff0c;而不是一条线走到底的那种#xff0c;所以深度优先搜索不适合
方法一#xff1a;bfs层序遍历
广度优先搜索#xff0c;就是从起点出发#xff0c;每次都尝… 文章目录 题目方法一bfs层序遍历 题目 该题值推荐用bfs因为是一层一层的感染而不是一条线走到底的那种所以深度优先搜索不适合
方法一bfs层序遍历
广度优先搜索就是从起点出发每次都尝试访问同一层的节点如果同一层都访问完了再访问下一层最后广度优先搜索找到的路径就是从起点开始的最短合法路径。
在该题假设图中只有一个腐烂的橘子它每分钟向外拓展腐烂上下左右相邻的新鲜橘子那么下一分钟就是这些被腐烂的橘子再向外拓展腐烂相邻的新鲜橘子这与广度优先搜索的过程均一一对应上下左右相邻的新鲜橘子就是该腐烂橘子尝试访问的同一层的节点路径长度就是新鲜橘子被腐烂的时间。
class Solution {
// 方法一 : bfs int m 0;int n 0;// 全局 格子宽度和长度int minute 0;//全局 最小分钟数int fulash 0;// 记录1的个数public int orangesRotting(int[][] grid) {m grid.length;n grid[0].length;Queueint[] queue new LinkedList();for(int i 0; im ; i)for(int j 0; jn ; j){if(grid[i][j] 1 ) fulash;//记录新鲜橘子的个数if(grid[i][j] 2 ){grid[i][j] 2;queue.offer(new int[]{i,j});//将坏橘子坐标数组 存入队列}}//层序遍历while(!queue.isEmpty() fulash 0){// 当队列空了 或者 没有新鲜橘子了停止循环int size queue.size();minute;// 一层一层的传染每传染一层时间1for(int i 0 ; isize ;i){int[] mid queue.poll();int x mid[0];int y mid[1];//上if(x1 m grid[x1][y] 1 ){fulash--; // 每传染一个更新新鲜橘子的数量grid[x1][y] 2;//将新鲜果子感染queue.offer(new int[]{x1,y});//将感染的果子加入队列进行下一层的处理}//下if(x-1 0 grid[x-1][y] 1 ){fulash--;grid[x-1][y] 2;queue.offer(new int[]{x-1,y});}//右if(y1 n grid[x][y1] 1 ){fulash--;grid[x][y1] 2;queue.offer(new int[]{x,y1});}//左if(y-1 0 grid[x][y-1] 1 ){fulash--;grid[x][y-1] 2;queue.offer(new int[]{x,y-1}); }}}if(fulash 0) return -1;//若还有新鲜橘子 则返回-1else return minute;//无新鲜橘子 则返回minute}}
