【算法】【优选算法】BFS 解决 FloodFill 算法
目录
一、FloodFill 算法简介
FloodFill 算法，可以理解为根据洪水蔓延，以点覆面，在这个过程中对涉及的一些问题求解。
二、733. 图像渲染
题目链接：733. 图像渲染
题目描述：
题目解析：
- 相当于给我们一个二维数组，和指定一个数组中的值为“母体”，当该位置上下左右四个方向初始值相同，就改为指定值（被传染），依次类推下去，直到全部感染或者传染不了。
解题思路：
- 利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可.
- 也就是我们使用一个队列，记录下来所有母体，出去一个母体，就将能传染的四个位置记录进队列。
- 注意下标问题，和当全部颜色都相同时，会超出时间限制，单独处理。
解题代码：
//时间复杂度：O(N)//空间复杂度：O(N)classSolution{publicint[][]floodFill(int[][] image,int sr,int sc,int color){//记录开始颜色int pre = image[sr][sc];//实例二排除if(pre == color)return image;Queue<int[]> queue =newLinkedList<>(); queue.add(newint[]{sr,sc});//对队列进行操作，直到空while(!queue.isEmpty()){int[] cur = queue.poll();int x = cur[0];int y = cur[1];//下标合法且颜色相同，传染，记录上下左右if(x >=0&& x < image.length && y >=0&& y < image[0].length && pre == image[x][y]){ image[x][y]= color; queue.add(newint[]{x-1, y}); queue.add(newint[]{x+1, y}); queue.add(newint[]{x, y-1}); queue.add(newint[]{x, y+1});}}return image;}}三、200. 岛屿数量
题目链接：200. 岛屿数量
题目描述：
题目解析：
- 就是给我们一个二位字符数组，让我们求相邻字符‘1’有多少块。
解题思路：
- 使用宽搜的思路，将每个数组元素都遍历一遍。
- 每一次都遍历字符数组去找到每一个岛屿的登陆地，也就是每一块1的第一个1。
- 我们引入一个标记数组（尽量不改变原数组），标记进过队列的字符数组元素下标，标记字符为0的数组下标，当标记数组全为修改后的true时，就可以返回值了。
- 写一个死循环包含上里面的逻辑，当数组全部为0的时候结束。
解题代码：
//时间复杂度：O(M*N)//空间复杂度：O(M*N)classSolution{int[] dx =newint[]{0,0,1,-1};int[] dy =newint[]{1,-1,0,0};boolean[][] vis;publicintnumIslands(char[][] grid){int m = grid.length;int n = grid[0].length; vis =newboolean[m][n];Queue<int[]> queue =newLinkedList<>();int ret =0;//死循环while(true){//找到第一个1，作为“登陆点”for(int i =0; i < m; i++){//标记break出循环boolean flag =false;for(int j =0; j < n; j++){if('1'== grid[i][j]&&!vis[i][j]){ queue.add(newint[]{i,j}); vis[i][j]=true; flag =true;break;}//所有vis元素都是true，返回if((i == m -1)&&(j == n -1)){return ret;} vis[i][j]=true;}if(flag)break;}//进行宽搜，找寻岛屿，并且修改岛屿值为0while(!queue.isEmpty()){int[] arr = queue.poll();//向量法找寻周围1 入队列for(int i =0; i <4; i++){int x = arr[0]+ dx[i];int y = arr[1]+ dy[i];//下标合法，字符数组元素为1，且并没有被访问，下标入队 if(x >=0&& x < m && y >=0&& y < n &&'1'== grid[x][y]&&!vis[x][y]){ vis[x][y]=true; queue.add(newint[]{x,y});}}} ret++;}}}四、695. 岛屿的最⼤⾯积
题目链接：695. 岛屿的最⼤⾯积
题目描述：
题目解析：
- 跟上一道题思路一样
解题思路：
- 在上一道题中没出一个队列元素计算面积的值加一即可。
解题代码:
//时间复杂度：O(M*N)//空间复杂度：O(M*N)classSolution{int[] dx ={0,0,1,-1};int[] dy ={1,-1,0,0};boolean[][] vis;publicintmaxAreaOfIsland(int[][] grid){int m = grid.length;int n = grid[0].length; vis =newboolean[m][n];int ret =0;Queue<int[]> queue =newLinkedList<>();while(true){int size =0;for(int i =0; i < m; i++){boolean flag =false;for(int j =0; j < n; j++){//登陆点if(1== grid[i][j]&&!vis[i][j]){ queue.add(newint[]{i,j}); vis[i][j]=true; flag =true;System.out.println(i+" "+j+"如队列");break;}//结束条件if(i == m -1&& j == n -1){System.out.println("结束条件 "+i+" "+j);if(grid[i][j]==1) size++;returnMath.max(ret, size);} vis[i][j]=true;}if(flag)break;}//计算面积while(!queue.isEmpty()){int[] arr = queue.poll(); size++;int x = arr[0];int y = arr[1];//查看周边for(int i =0; i <=3; i++){int a = x + dx[i];int b = y + dy[i];if(a >=0&& a < m && b >=0&& b < n &&!vis[a][b]&&1== grid[a][b]){ queue.add(newint[]{a,b}); vis[a][b]=true;}}} ret =Math.max(ret, size);}}}五、130.被围绕的区域
题目链接：130.被围绕的区域
题目描述：
题目解析：
- 给我们一个字符数组，让我们将被完全由X字符包围的O改为X
- 可以理解为只要字符数组边缘为O所在的岛屿留下，其它全变成X
解题思路：
- 我们只需要遍历字符数组边缘元素，有O，那么就进行宽搜，将宽搜到的字符进行标记。
- 我们引入一个与字符数组同等规模的标记数组，将能留下的O标记。
- 最后在遍历一遍字符数组，将没有被标记的字符全改为X即可。
解题代码：
//时间复杂度：O(M*N)//空间复杂度：O(M*N)classSolution{int[] dx ={0,0,1,-1};int[] dy ={1,-1,0,0};boolean[][] flag;int m,n;publicvoidsolve(char[][] board){ m = board.length; n = board[0].length; flag =newboolean[m][n];//只遍历边缘字符元素for(int i =0; i < m; i++){for(int j =0; j < n; j++){if((i ==0|| i == m -1|| j ==0|| j == n -1)&&'O'== board[i][j]&&!flag[i][j]){bfs(board, i, j);}}}//将被包围的字符改为Xfor(int i =0; i < m; i++){for(int j =0; j < n; j++){if(board[i][j]=='O'&&!flag[i][j]) board[i][j]='X';}}}//宽搜符合条件的不被包围字符publicvoidbfs(char[][] board,int x,int y){Queue<int[]> queue =newLinkedList<>(); queue.add(newint[]{x,y}); flag[x][y]=true;while(!queue.isEmpty()){int[] arr = queue.poll();for(int i =0; i <4; i++){int a = dx[i]+ arr[0];int b = dy[i]+ arr[1];if(a >=0&& a < m && b >=0&& b < n &&'O'== board[a][b]&&!flag[a][b]){ queue.add(newint[]{a,b}); flag[a][b]=true;}}}}}
