网站qq代码生成,wordpress摘要插件 帕兰映像,上海做网络口碑优化的公司,wordpress 优酷视频孤岛系列有#xff1a;
孤岛总面积求解#xff08;用了dfs、bfs两种方法#xff09;和沉没孤岛#xff08;这里只写了dfs一种#xff09; 简单解释一下#xff1a;
题目中孤岛的定义是与边缘没有任何接触的#xff08;也就是不和二维数组的最外圈连接#xff09;
孤岛总面积求解用了dfs、bfs两种方法和沉没孤岛这里只写了dfs一种 简单解释一下
题目中孤岛的定义是与边缘没有任何接触的也就是不和二维数组的最外圈连接所以我们在这里求面积和沉没孤岛都是先把不是孤岛的剔除 然后剩下的就是孤岛然后处理起来就简单多了那么我们这里是怎么遍历不是孤岛的岛呢很简单与数组外圈的1相连的肯定就不是孤岛所以我们直接从四个方向的边缘遍历将他们都处理掉。 其实都是dfs、bfs的模板题、基础题都比较简单这里贴出代码太懒了都写在了一个代码里...
题目、题解链接代码随想录
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class TheSquareOfIsolatedIsland {public static int ans0;public static int[][] next{{1,0},{0,1},{-1,0},{0,-1}};// dfs遍历计算孤岛面积public static void dfs(int[][] grid,int x,int y){grid[x][y]0;ans;for(int i0;i4;i){int nextXxnext[i][0];int nextYynext[i][1];if(nextX0||nextXgrid.length||nextY0||nextYgrid[0].length||grid[nextX][nextY]0) continue;dfs(grid,nextX,nextY);}}// bfs遍历计算孤岛面积public static void bfs(int[][] grid,int x,int y){Queueint[] queuenew LinkedList();queue.add(new int[] {x,y});grid[x][y]0;ans;while(!queue.isEmpty()){int[] theNextqueue.poll();int xxtheNext[0];int yytheNext[1];for(int i0;i4;i){int nextXxxnext[i][0];int nextYyynext[i][1];if(nextX0||nextXgrid.length||nextY0||nextYgrid[0].length||grid[nextX][nextY]0) continue;queue.add(new int[] {nextX,nextY});ans;grid[nextX][nextY]0;}}}// 沉没孤岛public static void dfs2(int[][] grid,int x,int y){grid[x][y]-1;for(int i0;i4;i){int nextXxnext[i][0];int nextYynext[i][1];if(nextX0||nextY0||nextXgrid.length||nextY grid[0].length) continue;if(grid[nextX][nextY]0||grid[nextX][nextY]-1) continue;dfs2(grid,nextX,nextY);}}public static void main(String[] args){Scanner scannernew Scanner(System.in);int nscanner.nextInt();int mscanner.nextInt();int[][] gridnew int[n][m];for(int i0;in;i){for(int j0;jm;j){grid[i][j]scanner.nextInt();}}scanner.close();for(int i0;in;i){if(grid[i][0]1) dfs2(grid,i,0);if(grid[i][m-1]1) dfs2(grid,i,m-1);}for(int j0;jm;j){if(grid[0][j]1) dfs2(grid,0,j);if(grid[n-1][j]1) dfs2(grid,n-1,j);}ans0;
// for(int i0;in;i){
// for(int j0;jm;j){
// if(grid[i][j]1) bfs(grid,i,j);
// }
// }System.out.println(ans);// 沉没孤岛输出操作for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1) grid[i][j]1;if(grid[i][j]-1) grid[i][j]0;}}for(int i0;in;i){for(int j0;jm;j){System.out.print(grid[i][j] );}System.out.println();}}
}
