【广度优先搜索】FloodFill算法： 图像渲染，岛屿数量，岛屿的最大面积，被围绕的区域

1. 图像渲染（LC733）

图像渲染

题目描述

解题思路

从起点向四个方向，类似层序遍历，一层一层开始搜索

代码实现

classSolution{publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intprev=image[sr][sc];if(prev==color)returnimage;intm=image.length;intn=image[0].length;int[]dx={1,-1,0,0};int[]dy={0,0,1,-1};Queue<int[]>queue=newLinkedList<>();queue.offer(newint[]{sr,sc});while(!queue.isEmpty()){int[]top=queue.poll();inti=top[0];intj=top[1];image[i][j]=color;for(intk=0;k<4;k++){intx=i+dx[k];inty=j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)queue.offer(newint[]{x,y});}}returnimage;}}

2. 岛屿数量（LC200）

岛屿数量

题目描述

代码实现

classSolution{publicintnumIslands(char[][]grid){Queue<int[]>queue=newLinkedList<>();intm=grid.length;intn=grid[0].length;boolean[][]check=newboolean[m][n];intret=0;int[]dx={1,-1,0,0};int[]dy={0,0,1,-1};for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(!check[i][j]&&grid[i][j]=='1'){ret++;check[i][j]=true;queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]top=queue.poll();intii=top[0];intjj=top[1];for(intk=0;k<4;k++){intx=ii+dx[k];inty=jj+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&grid[x][y]=='1'){queue.offer(newint[]{x,y});check[x][y]=true;}}}}}}returnret;}}

3. 岛屿的最大面积（LC695）

岛屿的最大面积

题目描述

代码实现

classSolution{publicintmaxAreaOfIsland(int[][]grid){intm=grid.length;intn=grid[0].length;boolean[][]check=newboolean[m][n];int[]dx={0,0,1,-1};int[]dy={1,-1,0,0};intret=0;Queue<int[]>queue=newLinkedList<>();for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(!check[i][j]&&grid[i][j]==1){check[i][j]=true;queue.offer(newint[]{i,j});intarea=1;while(!queue.isEmpty()){int[]top=queue.poll();intii=top[0];intjj=top[1];for(intk=0;k<4;k++){intx=ii+dx[k];inty=jj+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!check[x][y]&&grid[x][y]==1){queue.offer(newint[]{x,y});check[x][y]=true;area++;}}}ret=Math.max(ret,area);}}}returnret;}}

4. 被围绕的区域（LC130）

被围绕的区域

题目描述

解题思路

由于边界的O难处理，可以先遍历边界，对边界进行广度优先遍历，修改为'.'，接着对数组进行遍历，如果遇到'O'可以直接修改为'x'；遇到'.'可以直接修改为'O'

代码实现

classSolution{Queue<int[]>queue=newLinkedList();intm,n;int[]dx={0,0,1,-1};int[]dy={1,-1,0,0};publicvoidsolve(char[][]board){m=board.length;n=board[0].length;for(inti=0;i<m;i++){if(board[i][0]=='O')bfs(board,i,0);if(board[i][n-1]=='O')bfs(board,i,n-1);}for(intj=0;j<n;j++){if(board[0][j]=='O')bfs(board,0,j);if(board[m-1][j]=='O')bfs(board,m-1,j);}for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(board[i][j]=='O')board[i][j]='X';if(board[i][j]=='.')board[i][j]='O';}}}voidbfs(char[][]board,inti,intj){queue.offer(newint[]{i,j});board[i][j]='.';while(!queue.isEmpty()){int[]top=queue.poll();intii=top[0];intjj=top[1];for(intk=0;k<4;k++){intx=ii+dx[k];inty=jj+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O'){board[x][y]='.';queue.offer(newint[]{x,y});}}}}}