BFS算法解决FloodFill问题

BFS算法解决FloodFill问题图像渲染岛屿数量岛屿的最大面积被围住的区域图像渲染题目解析就是将这里面指定一个元素将其上下左右和这个一样的值全部修改成另外一个值并且其上下左右也可以进行上下左右进行扩展也就是将这个一片区域都修改成color指定值BFS直接遍历所有下标并且看其上下左右下标不断进行修改不断进行扩展延申此时就可以使用队列放入 int[ ] 数组对应存放行、列下标每一次不断取出进行上下左右延申判断其是否和image[sr][sc]如果一样就继续放入队列中不断进行操作直到队列为空这里通过上下左右对应下标分别classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};publicint[][]floodFill(int[][]image,intsr,intsc,intcolor){intprevimage[sr][sc];if(prevcolor){//如果要修改和修改的一样此时就不需要修改returnimage;}intmimage.length;intnimage[0].length;//存放其下标Queueint[]queuenewLinkedList();queue.add(newint[]{sr,sc});while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];//行intbtem[1];//列//将这个颜色修改image[a][b]color;//看这个位置前后左右位置for(inti0;i4;i){intxadx[i];intybdy[i];if(x0xmy0ynimage[x][y]prev){queue.add(newint[]{x,y});}}}returnimage;}}岛屿数量题目解析此时1表示岛屿并且1的上下左右如果有1的话就会进行延申展开最终求出有多少岛屿BFS遍历整个数组但是此时一个岛屿需要延申到不能延申为止这样才成为一个岛屿此时会出现问题我们会不断扩展后面遍历到这个位置又会让其岛屿数量1此时就重复统计了这里有两种解决方案方案一每次遍历过的位置将这里的 1 修改成 0方案二创建一个同等规模的数组如果统计过了就进行标记一下classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};boolean[][]visited;//标记已经遍历过的位置intm0;intn0;publicintnumIslands(char[][]grid){mgrid.length;ngrid[0].length;visitednewboolean[m][n];intret0;for(inti0;im;i){for(intj0;jn;j){//当时1并且没有遍历过结果if(grid[i][j]1visited[i][j]false){ret;dfs(grid,i,j);//将其旁边的visited都标记为遍历过}}}returnret;}publicvoiddfs(char[][]grid,inti,intj){Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});visited[i][j]false;while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];if(x0xmy0yngrid[x][y]1!visited[x][y]){queue.add(newint[]{x,y});visited[x][y]true;}}}}}岛屿的最大面积题目解析就是找出岛屿最大面积思想此时和上一题岛屿数量类似此时我们只需要在dfs方法中返回此时岛屿数量即可classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};boolean[][]visited;//标记已经遍历过的intm0;intn0;publicintmaxAreaOfIsland(int[][]grid){intret0;mgrid.length;ngrid[0].length;visitednewboolean[m][n];//此时遍历这个岛屿的时候统计一下它的面积返回for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1visited[i][j]false){//此时更新结果retMath.max(ret,dfs(grid,i,j));}}}returnret;}publicintdfs(int[][]grid,inti,intj){intcount0;//此时岛屿面积Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});visited[i][j]true;count;while(!queue.isEmpty()){//队列为空就结束int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];//延申if(x0xmy0yngrid[x][y]1visited[x][y]false){queue.add(newint[]{x,y});visited[x][y]true;count;}}}returncount;}}被围住的区域题目解析就是将被X围住的O修改成X,未被围住的不做修改思想由于以前是一边遍历一边修但是这里会出现不需要修改的问题可能修改一半发现不需要修改此时这里还需要进行二次判断因此这里采用正难则反的思想1.先使用dfs遍历边界此时将边界及其扩展部分修改成 其他字符2.最后遍历一遍数组将剩下未被修改的O修改成X将这里被修改成其他字符的修改回以前的O字符classSolution{int[]dx{0,0,1,-1};int[]dy{1,-1,0,0};intm0;intn0;publicvoidsolve(char[][]board){mboard.length;nboard[0].length;//1.将边界的O以及相邻的O全部修改成 . 最后在修改回来//左右两列for(inti0;im;i){if(board[i][0]O){dfs(board,i,0);}if(board[i][n-1]O){dfs(board,i,n-1);}}//上下两行for(inti0;in;i){if(board[0][i]O){dfs(board,0,i);}if(board[m-1][i]O){dfs(board,m-1,i);}}//剩下的O修改成X将上面修改的还原for(inti0;im;i){for(intj0;jn;j){if(board[i][j]O){board[i][j]X;//修改回来}elseif(board[i][j].){board[i][j]O;}}}}publicvoiddfs(char[][]board,inti,intj){Queueint[]queuenewLinkedList();queue.add(newint[]{i,j});board[i][j].;//修改成.while(!queue.isEmpty()){int[]temqueue.poll();intatem[0];intbtem[1];for(intk0;k4;k){intxadx[k];intybdy[k];if(x0xmy0ynboard[x][y]O){queue.add(newint[]{x,y});board[x][y].;}}}}}