java算法day25
- 广度优先搜索
- 岛屿数量深搜
- 岛屿数量广搜
- 994 腐烂的橘子
广度优先搜索
核心：从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。搜索的方式是上下左右
一张图说明白模拟过程：
每一层，每个点不停的往上下左右的方向扩。
在面对有障碍的情况下也同样如此：
所以可以得出一个结论：
因为bfs这种一圈一圈层层往外搜索的性质，决定了bfs处理得到的路径一定是一条最短路径。
那这种一圈一圈的搜索过程是怎么做到的，用了什么容器才能实现这样的遍历。
回答是：用队列，栈，数组都可以。但是这里习惯用队列。
用队列那就是保证每一圈都是一个方向去转，例如统一顺时针或者统一逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序没有发生改变。
而且顺时针和逆时针转都是可以的，并不用做什么特殊处理。
接下来是一个队列的模板。看看用队列怎么完成bfs。
import java.util.*; class Solution { // 表示四个方向：右、下、上、左 private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // grid 是地图，是一个二维字符数组 // visited 标记访问过的节点，避免重复访问 // x, y 表示开始搜索节点的坐标 public void bfs(char[][] grid, boolean[][] visited, int x, int y) { //定义队列，该队列用于BFS，其中存的都是点Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{x, y}); // 起始节点加入队列 visited[x][y] = true; // 标记起始节点为已访问 //BFS主循环，当队列不空时，继续搜索while (!queue.isEmpty()) {//从队列中把要处理的点取出来，x坐标是cur[0],y坐标是cur[1]。这里把要处理的点的坐标拿出来是为了方便等下做上下左右运算。 int[] cur = queue.poll(); int curx = cur[0]; int cury = cur[1]; // 遍历四个方向：右、下、上、左 //这里相当于处理当前节点，for (int[] d : dir) {//为了方便还是计算该节点下一步要走的坐标。分别计算横坐标和纵坐标 int nextx = curx + d[0]; int nexty = cury + d[1]; //这个点算出来了 检查是否越界，看看这个点是否合法 if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {//如果这里面有一个不满足就代表这个点不合法，那么就不处理，所以跳过处理该方向的点。continue; } //能走到这里说明点是合法的，但是还要看看这个点之前访问过了没。直接通过这个标记数组进行检查即可// 如果下一个节点没有被访问过，就会进去if (!visited[nextx][nexty]) {//然后把这个没访问的节点放入待处理的队列中 queue.offer(new int[]{nextx, nexty});//然后把该点设置为已经访问 visited[nextx][nexty] = true; // 在这里可以根据具体问题进行额外的处理 }//到了这里就会发现，循环里的某方向的一个点处理，而且还把该节点加入到了队列里。因为之后处理这个节点，往外面的方向扩的过程就是上面模拟的bfs。//这里一个方向就已经处理完毕，下一个循环就是下一个方向了。所以依次类推，就是一圈一圈的往外处理。//以中间的这个点来模拟，左方向处理完后加入了队列，然后假设转了一圈，跳转下一个节点的时候，从队列里第一个弹出来的节点就是这个左方向的节点，他也是如此的方式进行模拟。 } } }
}
我学完这个模板之后，我感觉特别像层序遍历。不过是在图的角度上。
使用这个模板的步骤：
定义问题的网格（grid）。
创建一个与网格大小相同的 visited 数组。
选择起始位置（x, y）。
调用 bfs 方法。
岛屿数量深搜
题目已经说了，只有水平和竖直方向算，斜角度不算连着。这和遍历四个方向的考虑一致了。
算法思想：
1、遍历整个网格
2、当找到一个未访问的陆地时，将岛屿计数+1
3、然后调用DFS标记与这个陆地相连的所有陆地为已访问（用dfs就是递归，但是还是有一点BFS的影子，直接往四个方向都递归，当遇到节点是0就停下，或者节点不合法了也停下）
4、重复这个过程直到遍历完整个网络（相当于把整个网格都处理了。）
这种方法是可以有效的计算岛屿数量，因为每个岛屿只会被计数一次，而与他相连的所有陆地都会在dfs的过程中被标记。
import java.util.Scanner; public class Main{//规定四个方向,方便用来计算四个要遍历的方向static final int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};//主方法public static void main(String[] args){//定义网格Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){grid[i][j] = scanner.nextInt();}}//定义标记网格和计数器boolean[][] visited = new boolean[n][m];int result = 0;//遍历所有网格for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){//遍历的过程中，如果遇到陆地，并且没有访问过，那就意味着这是一个新岛屿，所以先计数器++，然后dfs。把该陆地上所有相邻陆地全部标记为已经访问。if(!visited[i][j] && grid[i][j]==1){result++;//就是dfs这个第一个遇见的陆地，之后会dfs把相邻的陆地全部置为已经访问dfs(grid,visited,i,j);}}}//结果输出System.out.println(result);}public static void dfs(int[][] grid,boolean[][] visited,int x,int y){//这里我写递归出口是已经考虑了，我是遇到了第一个陆地网格才进来的//所以这里递归出口的条件就会松一点。if(visited[x][y] || grid[x][y]==0){return;}//先处理当前节点,这里要进行处理就是把他置为truevisited[x][y] = true;//然后遍历四个方向，每个方向都要进行dfsfor(int[] d:dir){//dfs之前，把要dfs的坐标算出来int nextX = x+d[0];int nextY = y+d[1];//在进行dfs之前，还要判断这个方向的节点是否合法。//不合法就跳过了。if(nextX<0 || nextX>=grid.length || nextY<0 || nextY>=grid[0].length){continue;}//合法就dfsdfs(grid,visited,nextX,nextY);}}
}
岛屿数量广搜版
做这个题的时候，有一个细节需要特别的注意
只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。如果用了后面这种方式，会导致同一节点被多次加入队列。
具体场景如下：
1 1 1
1 1 1
1 1 1
从左上角开始BFS，如果我们在将节点从队列拿出来的时候再去标记。那么
(0,0)加入队列
从队列中取出(0,0)，标记为已经访问
然后BFS将(0,1)和(1,0)加入队列
从队列中取出(0,1)标记为已访问。
然后将(0,1)的邻居(0,2),(1,1)加入队列。
接下来从队列中取出(1,0)然后并标记为已经访问
将(1,0)的邻居加入队列，此时就包含了(1,1)
问题就来了，(1,1)被重复加入队列。
这就是会出现重复的问题，在更大的网格中，这种重复会更加的严重。
队列中会产生大量的重复节点，每个节点会被处理多次，导致算法效率大大降低甚至超时。
所以，应该在加入队列的同时，标记为已经访问。这样当考虑将某点加入队列的时候，发现已经标记过了就不会再重复加入了。
算法思想：
整体来说和DFS的解法一致。就是visited标记那里改成了用bfs的方式来做。
import java.util.*; public class Main { private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向 private static void bfs(int[][] grid, boolean[][] visited, int x, int y) { Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{x, y}); visited[x][y] = true; // 只要加入队列，立刻标记 //迭代的本质，和层序遍历非常相似，队列不空就不停while (!queue.isEmpty()) { //取出节点int[] cur = queue.poll(); int curx = cur[0]; int cury = cur[1]; //处理四个方向for (int[] d : dir) { //计算下一个方向的节点，准备将他加入队列中。int nextx = curx + d[0]; int nexty = cury + d[1]; //计算出来的这个节点，还要进行安全性判断if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了，直接跳过 //然后再经过是否标记过，是否是岛屿的判断。才能将这个节点标记为true并加入队列if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { queue.offer(new int[]{nextx, nexty}); visited[nextx][nexty] = true; // 只要加入队列立刻标记 } } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] grid = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { grid[i][j] = scanner.nextInt(); } } boolean[][] visited = new boolean[n][m]; int result = 0; //算法的核心思想，就是遍历网格。每遇到一个陆地，并且还没访问过//就统计+1，并且将其相邻陆地按照dfs或者bfs标记为已访问。for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j] && grid[i][j] == 1) { result++; // 遇到没访问过的陆地，+1 bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true } } } System.out.println(result); }
}
200 岛屿数量
BFS解法：
class Solution {int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};public int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];int result = 0;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(!visited[i][j] && grid[i][j]=='1'){result++;bfs(grid,visited,i,j);}}}return result;}void bfs(char[][] grid,boolean[][] visited,int x,int y){//先创建一个队列Queue<int[]> que = new LinkedList<>();//第一个节点加入进去，加之前进行标记visited[x][y] = true;que.offer(new int[]{x,y});while(!que.isEmpty()){//开始取出队列的节点进行处理int[] cur = que.poll();int curX = cur[0];int curY = cur[1];//然后开始处理该节点的四个方向for(int[] d : dir){//通过方向计算该节点的上下左右，然后加入队列中int nextX = curX+d[0];int nextY = curY+d[1];//在加入队列之前还要进行合法性判断if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length){continue;}//还要判断该节点有没有访问过，并且是不是陆地节点if(!visited[nextX][nextY] && grid[nextX][nextY] == '1'){visited[nextX][nextY] = true;que.offer(new int[]{nextX,nextY});}}}}}
DFS解法：
class Solution {int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};public int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;boolean[][] visited = new boolean[n][m];int result = 0;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(!visited[i][j] && grid[i][j]=='1'){result++;dfs(grid,visited,i,j);}}}return result;}void dfs(char[][] grid,boolean[][] visited,int x,int y){if(grid[x][y] == '0' || visited[x][y]){return;}//先处理当前节点,先进行标记visited[x][y] = true;//然后处理四周for(int[] d : dir){int nextX = x+d[0];int nextY = y+d[1];//然后合法性判断if(nextX<0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length){continue;}//然后开始处理下一个节点dfs(grid,visited,nextX,nextY);}}}
994 腐烂的橘子
做这个题果然感受到了BFS和DFS就是两大利器。
首先就是对题目的直观感受：
由题意来分析，针对第一句话：**每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。**自己模拟一下就可以感觉出，是一种一圈圈往外扩散的感觉，那么这显然就想到了BFS。我们需要基于腐烂的橘子一圈圈往外的将新鲜橘子腐烂（就是一圈圈将网格中的数由1置为2，当然是新鲜橘子你才能这么做）。
然后因为能想到这样的场景：网格中分布着不同位置的腐烂橘子，所以这个腐烂的扩散是同时进行的。所以这个时候如何处理？
你肯定会这么想，先把所有腐烂的橘子找出来。然后同时对他们进行处理。这个“同时”我“定义为在同一分钟内进行处理”。所以这里怎么实现这个同时处理？
回答是用队列。
想想二叉树层序遍历的场景。
我开局把所有的腐烂橘子加入队列。然后记录此时的队列长度。不就是做到了把第一分钟要处理的所有腐烂橘子收集了起来，然后这轮for循环遍历完当前队列长度。就完成了第一分钟要腐烂的所有橘子的处理。
往后的操作依然如此。我们处理第一分钟的腐烂橘子的时候，把刚腐烂的加入队列中。当第一分钟的处理完之后，第二分钟要进行处理的橘子已经放到了队列中。
每处理完这样的一轮层序遍历就minutes++。
算法实现描述：
1、遍历整个网格，将所有腐烂的橘子（2）的位置加入队列，同时统计新鲜橘子的数量。
2、使用BFS，每一轮（代表一分钟）处理队列中的所有橘子，将它们周围的新鲜橘子腐烂并加入队列。
3、记录BFS的轮数，即为所需的分钟数。
最后检查是否还有新鲜橘子，如果有，返回-1；否则返回记录的分钟数。
具体来看代码细节：
代码中对尤其要关注某些特判的处理。非常的关键。这样的判断针对了不同的特殊情况。
主要就是三点非常重要的优化判断。
1、while(!que.isEmpty() && freshOranges > 0)
看代码的时候也许会疑惑，为什么要做这样的判断。这主要对性能优化有利。当新鲜橘子全部腐烂完的时候，有可能队列还没有空，那么不写这个条件，那就还要接着处理队列，但是你知道此时已经全部腐烂，再去处理队列是没有意义的。所以这里可以提前停下来，减少很多不必要的计算。
2、if(!que.isEmpty()){
minutes++;
}
这个判断条件主要针对一种特殊情况，有一种特殊情况，当开局所有橘子都是腐烂的，没有新鲜橘子，那么此时minutes = 0。如果不加这个判断，处理完第一轮就会直接minutes++。不符合结果。而!que.isEmpty()作为判断的条件，就是体现了还有扩散的过程。也就是处理完第一轮，队列里还有元素。
3、题目里还有一个要求：返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1
这个不可能是什么情况？
情况是存在孤立的新鲜橘子，这样烂橘子没办法将其腐烂。所以无法进行全部腐烂。
class Solution {public int orangesRotting(int[][] grid) {int rows = grid.length;int cols = grid[0].length;Queue<int[]> que = new LinkedList<>();int freshOranges = 0;int minutes = 0;//先找所有的烂橘子和统计所有的新鲜橘子for(int i = 0;i<rows;i++){for(int j = 0;j<cols;j++){if(grid[i][j] == 2){que.offer(new int[]{i,j});}else if(grid[i][j] == 1){freshOranges++;}}}//接下来就是开始处理队列进行BFS了int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};while(!que.isEmpty() && freshOranges > 0){//这里非常像层序遍历，因为要处理完这一分钟的烂橘子int size = que.size();for(int i = 0;i<size;i++){//依次弹出队头int[] point = que.poll();//然后处理该节点的四个方向for(int[] d : dir){int nextX = point[0]+d[0];int nextY = point[1]+d[1];//在对这个周围节点进行处理之前，还要判断合法性if(nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols){continue;}//能到这里说明合法性判断通过了。在进行腐烂操作之前还要判断是不是新鲜橘子，是才能赋值if(grid[nextX][nextY] == 1){grid[nextX][nextY] = 2;que.offer(new int[]{nextX,nextY});freshOranges--;}}}if(!que.isEmpty()){minutes++;}}if(freshOranges!=0){return -1;}return minutes;}
}
