算法题目---BFS解决FloodFill算法问题

(一).基础概念FloodFill算法也称为“洪水灌溉”算法。通过一个图来看此时方框表示一个区域其中里面的负数表示这个部分是往下凹的正数部分是往上凸的。如果此时发洪水了那么首先会将凹的部分填平此时就会出现上图的结果。然后就会问有多少部分被填平或者是被填平的最大部分是多少。事实上就是在找“性质相同的连通块”解决方法有两种①.dfs ②.bfsdfs深度优先遍历采用递归的方式一条路走到黑直到走不了的时候就返回bfs广度优先遍历也称为层序遍历一层一层的遍历对于广度优先遍历不同的题目有不同的要求。有些题目是找某个点的上下左右四个方向有些题目会找某个点的上下左右左上左下右上右下 八个方向(二).具体题目1.图像渲染733. 图像渲染 - 力扣LeetCode解法bfsclass Solution { public int[] dx{0,0,1,-1}; public int[] dy{1,-1,0,0}; public int[][] floodFill(int[][] image, int sr, int sc, int color) { int previmage[sr][sc]; //统计刚开始的颜色 if (prevcolor){ //处理边界情况如果prev调整之前的颜色和color调整之后的颜色一样则不需要调整 return image; } int lenRimage.length; int lenCimage[0].length; Queueint[] queuenew ArrayDeque(); //里面存数组的原因是保存下标 queue.add(new int[]{sr,sc}); while (!queue.isEmpty()){ int[] pollqueue.poll(); int xpoll[0]; int ypoll[1]; image[x][y]color; //找上下左右四个方向的值 for (int i 0; i 4; i) { int newXxdx[i]; int newYydy[i]; if (newX0 newXlenR newY0 newYlenC image[newX][newY]prev){ queue.add(new int[]{newX,newY}); } } } return image; } }2.岛屿数量200. 岛屿数量 - 力扣LeetCode解法bfsclass Solution { int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; boolean[][] visit;//标记数组用于标记已经遍历过的位置 public int numIslands(char[][] grid) { int ret0; int rowLengthgrid.length; int colLengthgrid[0].length; visitnew boolean[rowLength][colLength]; for (int i 0; i rowLength; i) { for (int j 0; j colLength; j) { if (grid[i][j]1 visit[i][j]false){ ret; bfs(grid,i,j); } } } return ret; } private void bfs(char[][] grid, int x, int y) { Queueint[] queuenew ArrayDeque(); queue.add(new int[]{x,y}); visit[x][y]true; while (!queue.isEmpty()){ int[] poll queue.poll(); int posxpoll[0]; int poxypoll[1]; for (int i 0; i 4; i) { int newXposxdx[i]; int newYpoxydy[i]; if (newX0 newXgrid.length newY0 newYgrid[0].length grid[newX][newY]1 visit[newX][newY]false){ queue.add(new int[]{newX,newY}); visit[newX][newY]true; } } } } }3.岛屿的最大面积695. 岛屿的最大面积 - 力扣LeetCode解法bfsclass Solution { int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; boolean[][] visit; public int maxAreaOfIsland(int[][] grid) { int maxInteger.MIN_VALUE; int rowLengthgrid.length; int colLengthgrid[0].length; visitnew boolean[rowLength][colLength]; for (int i 0; i rowLength; i) { for (int j 0; j colLength; j) { if (grid[i][j]1 visit[i][j]false){ maxMath.max(max,bfs(grid,i,j)); } } } return maxInteger.MIN_VALUE?0:max; } private int bfs(int[][] grid, int x, int y) { Queueint[] queuenew ArrayDeque(); queue.add(new int[]{x,y}); visit[x][y]true; int count1; while (!queue.isEmpty()){ int[] poll queue.poll(); int posxpoll[0]; int posypoll[1]; for (int i 0; i 4; i) { int newXposxdx[i]; int newYposydy[i]; if (newX0 newXgrid.length newY0 newYgrid[0].length grid[newX][newY]1 visit[newX][newY]false){ queue.add(new int[]{newX,newY}); visit[newX][newY]true; count; } } } return count; } }4.被围绕的区域130. 被围绕的区域 - 力扣LeetCode解法正难则反class Solution { int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; public void solve(char[][] board) { int lenRboard.length; int lenCboard[0].length; for (int i 0; i lenC; i) { if (board[0][i]O){ //遍历第0行 board[0][i]1; bfs(board,0,i); } if (board[lenR-1][i]O){ //遍历最后一行 board[lenR-1][i]1; bfs(board,lenR-1,i); } } for (int i 0; i lenR; i) { if (board[i][0]O){ //遍历第0列 board[i][0]1; bfs(board,i,0); } if (board[i][lenC-1]O){ //遍历最后一列 board[i][lenC-1]1; bfs(board,i,lenC-1); } } //还原 for (int i 0; i lenR; i) { for (int j 0; j lenC; j) { if (board[i][j]O){ board[i][j]X; } if (board[i][j]1){ board[i][j]O; } } } } private void bfs(char[][] board, int x, int y) { Queueint[] queuenew ArrayDeque(); queue.add(new int[]{x,y}); board[x][y]1; while (!queue.isEmpty()){ int[] poll queue.poll(); int posXpoll[0]; int posYpoll[1]; for (int i 0; i 4; i) { int newXposXdx[i]; int newYposYdy[i]; if (newX0 newXboard.length newY0 newYboard[0].length board[newX][newY]O){ queue.add(new int[]{newX,newY}); board[newX][newY]1; } } } } }