算法打卡：第十一章图论part03

今日收获：孤岛的总面积，沉没孤岛，水流问题，建造最大岛屿

1. 孤岛的总面积

题目链接：101. 孤岛的总面积

思路：只要岛屿中有一个节点是边缘节点，那么这个岛屿就不是孤岛，结果不累加其面积。在深度优先函数中总共有三个地方需要判断：

（1）当前传入节点是否是边缘节点

（2）在下个节点进行深度优先遍历之前，判断这个节点是否是边缘节点

（3）根据深度优先遍历的返回值判断，如果深度优先遍历的过程中出现了边缘节点，则当前岛屿也不是孤岛。

方法：

java">import java.util.Scanner;public class Main{static int current;static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}boolean[][] visited=new boolean[N][M];int result=0;for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (!visited[i][j]&&grid[i][j]==1){current=0;  // 当前岛屿的面积visited[i][j]=true;if (dfs(visited,i,j,grid)){  // 如果是孤岛result+=current;}}}}System.out.println(result);}public static boolean dfs(boolean[][] visited,int x,int y,int[][] grid){boolean flag=true;  // 是否为孤岛current++;  // 计算当前岛屿的面积if (x==0||y==0||x==grid.length-1||y==grid[0].length-1){flag=false;}for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){if (nextX==0||nextY==0||nextX==grid.length-1||nextY==grid[0].length-1){flag=false;}visited[nextX][nextY]=true;if (!dfs(visited,nextX,nextY,grid)){flag=false;}}}return flag;}
}

2. 沉没孤岛

题目链接：102. 沉没孤岛

思路：遍历格子的四条边，将边上相邻的陆地都标记为2。孤岛中的陆地还是原来的1。然后再把1变成0，2变成1，输出格子。（也可以看作是把不同的岛屿做了标记）

方法：

java">import java.util.Scanner;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}boolean[][] visited=new boolean[N][M];// 从格子四周遍历陆地，标记为2for (int i=0;i<grid.length;i++){  // 第0列和最后一列if (!visited[i][0]&&grid[i][0]==1){dfs(visited,i,0,grid);}if (!visited[i][M-1]&&grid[i][M-1]==1){dfs(visited,i,M-1,grid);}}for (int j=0;j<M;j++){  // 第一行和最后一行if (!visited[0][j]&&grid[0][j]==1){dfs(visited,0,j,grid);}if (!visited[N-1][j]&&grid[N-1][j]==1){dfs(visited,N-1,j,grid);}}// 将孤岛变为0，即grid中为1的格子for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (grid[i][j]==1){grid[i][j]=0;}}}// 将原来的岛屿变为1for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (grid[i][j]==2){grid[i][j]=1;}}}// 输出for (int i=0;i<N;i++){for (int j=0;j<M;j++){System.out.print(grid[i][j]+" ");}System.out.println(" ");}}public static void dfs(boolean[][] visited,int x,int y,int[][] grid){visited[x][y]=true;grid[x][y]=2;for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){dfs(visited,nextX,nextY,grid);}}}
}

3. 水流问题

题目链接：103. 水流问题

思路：从两组边界开始逆流而上，判断是否能到达其他格子。最后的结果是从两组边界出发逆流而上都能到达的格子。

方法：

java">import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;public class Main{static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);// 接收数据int N=sc.nextInt();int M=sc.nextInt();int[][] heights=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){heights[i][j]=sc.nextInt();}}// 两组边界分别能到达的点boolean[][] first=new boolean[N][M];boolean[][] second=new boolean[N][M];// 从两组边界开始逆流而上for (int i=0;i<N;i++){dfs(heights,first,i,0,Integer.MIN_VALUE);dfs(heights,second,i,M-1,Integer.MIN_VALUE);}for (int j=0;j<M;j++){dfs(heights,first,0,j,Integer.MIN_VALUE);dfs(heights,second,N-1,j,Integer.MIN_VALUE);}// 收集两组边界都能到达的格子List<int[]> result=new ArrayList<>();for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (first[i][j]&&second[i][j]){result.add(new int[]{i,j});}}}// 输出结果for (int [] pair:result){System.out.println(pair[0]+" "+pair[1]);}}public static void dfs(int[][] heights,boolean[][] visited,int x,int y,int pre){// 判定合法性if (heights[x][y]<pre){return;  // 不能逆流而上}// 访问当前节点和相邻节点visited[x][y]=true;for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];if (nextX<0||nextY<0||nextX>=heights.length||nextY>=heights[0].length){continue;}if (!visited[nextX][nextY]){dfs(heights,visited,nextX,nextY,heights[x][y]);}}}
}

4. 建造最大岛屿

题目链接：104. 建造最大岛屿

思路：

（1）同属于一个岛屿的格子用相同的数字标记，不同属于一个岛屿的格子标记不同。

（2）用map存储每个岛屿的编号和面积

（3）遍历格子中的0节点，判断其周围格子是否属于某一个岛屿，如果是则将周围岛屿的面积相加，结果遍历中相加结果的最大值

（4）注意：0节点的周围节点所属岛屿面积不能重复相加（周围四个节点其中可能有同属于一个岛屿的），要使用set集合存储相加过面积的岛屿编号

（5）如果格子中没有0节点，结果取所有岛屿面积的最大值（即最多只能变水为陆一次，没有就不变）

方法：

java">import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;public class Main{static int count=2;  // 岛屿编号static int current;  // 岛屿面积static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][] grid=new int[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){grid[i][j]=sc.nextInt();}}// 记录岛屿编号和面积HashMap<Integer,Integer> map=new HashMap<>();boolean[][] visited=new boolean[N][M];for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (!visited[i][j]&&grid[i][j]==1){  // 开始遍历新的岛屿current=0;dfs(visited,i,j,grid);map.put(count,current);count++;}}}int result=0;// 遍历格子中的0，判断其周围有没有岛屿，有的话加上面积// 注意岛屿编号不能重复访问HashSet<Integer> set=new HashSet<>();for (int i=0;i<N;i++){for (int j=0;j<M;j++){if (grid[i][j]==0){int area=1;for (int k=0;k<4;k++){int nextX=i+around[k][0];int nextY=j+around[k][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}if (map.containsKey(grid[nextX][nextY])&&!set.contains(grid[nextX][nextY])){set.add(grid[nextX][nextY]);area+=map.get(grid[nextX][nextY]);}}result=Math.max(result,area);set.clear();}}}// 如果格子中没有0，取岛屿的最大面积for (int key:map.keySet()){result=Math.max(result,map.get(key));}System.out.println(result);}public static void dfs(boolean[][] visited,int x,int y,int[][] grid){visited[x][y]=true;grid[x][y]=count;current++;for (int i=0;i<4;i++){int nextX=x+around[i][0];int nextY=y+around[i][1];if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){continue;}if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){dfs(visited,nextX,nextY,grid);}}}
}