图论基础--孤岛系列

孤岛系列有：

孤岛总面积求解（用了dfs、bfs两种方法）和沉没孤岛（这里只写了dfs一种）

简单解释一下：

题目中孤岛的定义是与边缘没有任何接触的（也就是不和二维数组的最外圈连接），所以我们在这里求面积和沉没孤岛都是先把不是孤岛的剔除 ，然后剩下的就是孤岛，然后处理起来就简单多了，那么我们这里是怎么遍历不是孤岛的岛呢，很简单，与数组外圈的1相连的肯定就不是孤岛，所以我们直接从四个方向的边缘遍历将他们都处理掉。

其实都是dfs、bfs的模板题、基础题，都比较简单，这里贴出代码（太懒了，都写在了一个代码里...）

题目、题解链接：代码随想录

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class TheSquareOfIsolatedIsland {public static int ans=0;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 i=0;i<4;i++){int nextX=x+next[i][0];int nextY=y+next[i][1];if(nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[0].length||grid[nextX][nextY]==0) continue;dfs(grid,nextX,nextY);}}//    bfs遍历计算孤岛面积public static void bfs(int[][] grid,int x,int y){Queue<int[]> queue=new LinkedList<>();queue.add(new int[] {x,y});grid[x][y]=0;ans++;while(!queue.isEmpty()){int[] theNext=queue.poll();int xx=theNext[0];int yy=theNext[1];for(int i=0;i<4;i++){int nextX=xx+next[i][0];int nextY=yy+next[i][1];if(nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[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 i=0;i<4;i++){int nextX=x+next[i][0];int nextY=y+next[i][1];if(nextX<0||nextY<0||nextX>=grid.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 scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();int[][] grid=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){grid[i][j]=scanner.nextInt();}}scanner.close();for(int i=0;i<n;i++){if(grid[i][0]==1) dfs2(grid,i,0);if(grid[i][m-1]==1) dfs2(grid,i,m-1);}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs2(grid,0,j);if(grid[n-1][j]==1) dfs2(grid,n-1,j);}ans=0;
//        for(int i=0;i<n;i++){
//            for(int j=0;j<m;j++){
//                if(grid[i][j]==1) bfs(grid,i,j);
//            }
//        }System.out.println(ans);//        沉没孤岛输出操作for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1) grid[i][j]=1;if(grid[i][j]==-1) grid[i][j]=0;}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){System.out.print(grid[i][j]+" ");}System.out.println();}}
}