devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录Day66（图论Part03）

作者：码创造者 | 2024-07-10 05:05:52

赞

踩

代码随想录Day66（图论Part03）

101.孤岛的总面积

题目：101. 孤岛的总面积 (kamacoder.com)

思路：无

答案
  1. import java.util.Scanner;
  2.  
  3. class Main {
  4.     private static int N, M;
  5.     private static int[][] grid;
  6.     private static boolean[][] visited;
  7.     private static boolean touchesEdge;
  8.  
  9.     public static void main(String[] args) {
  10.         Scanner scanner = new Scanner(System.in);
  11.         N = scanner.nextInt();
  12.         M = scanner.nextInt();
  13.         grid = new int[N][M];
  14.         visited = new boolean[N][M];
  15.  
  16.         for (int i = 0; i < N; i++) {
  17.             for (int j = 0; j < M; j++) {
  18.                 grid[i][j] = scanner.nextInt();
  19.             }
  20.         }
  21.  
  22.         int totalIslandArea = 0;
  23.  
  24.         for (int i = 0; i < N; i++) {
  25.             for (int j = 0; j < M; j++) {
  26.                 if (grid[i][j] == 1 && !visited[i][j]) {
  27.                     touchesEdge = false;
  28.                     int islandArea = dfs(i, j);
  29.                     if (!touchesEdge) {
  30.                         totalIslandArea += islandArea;
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.  
  36.         System.out.println(totalIslandArea);
  37.     }
  38.  
  39.     private static int dfs(int x, int y) {
  40.         if (x < 0 || x >= N || y < 0 || y >= M) {
  41.             return 0;
  42.         }
  43.         if (grid[x][y] == 0 || visited[x][y]) {
  44.             return 0;
  45.         }
  46.  
  47.         if (x == 0 || x == N - 1 || y == 0 || y == M - 1) {
  48.             touchesEdge = true;
  49.         }
  50.  
  51.         visited[x][y] = true;
  52.         int area = 1;
  53.  
  54.         area += dfs(x + 1, y);
  55.         area += dfs(x - 1, y);
  56.         area += dfs(x, y + 1);
  57.         area += dfs(x, y - 1);
  58.  
  59.         return area;
  60.     }
  61. }
小结

在dfs里面需要判断岛屿时候接触边缘

102.沉没孤岛

题目：102. 沉没孤岛 (kamacoder.com)

思路：判断周围也没有岛屿，上下左右都没有，那就将当前位置变为0

尝试（标题4）
  1. import java.util.Scanner;
  2.  
  3. class Main{
  4.     public static int m;
  5.     public static int n;
  6.     public static int[][] grid;
  7.     public static boolean[][] visited;
  8.     public static void main(String[] args){
  9.         Scanner scanner = new Scanner(System.in);
  10.         n = scanner.nextInt();
  11.         m = scanner.nextInt();
  12.         grid = new int[n][m];
  13.         visited = new boolean[n][m];
  14.         
  15.         for(int i=0; i<n; i++){
  16.             for(int j=0; j<m; j++){
  17.                 grid[i][j] = scanner.nextInt();
  18.             }
  19.         }
  20.         
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < m; j++) {
  23.                 if (grid[i][j] == 1 && !visited[i][j]) {
  24.                     int area = dfs(i, j);
  25.                     if(area == 1) grid[i][j] = 0;
  26.                 }
  27.             }
  28.         }
  29.         
  30.         for (int i = 0; i < n; i++) {
  31.             for (int j = 0; j < m; j++) {
  32.                 System.out.print(grid[i][j]+" ");
  33.             }
  34.             System.out.println();
  35.         }
  36.         
  37.     }
  38.     private static int dfs(int i, int j) {
  39.         if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0 || visited[i][j]) {
  40.             return 0;
  41.         }
  42.         
  43.         visited[i][j] = true;
  44.         int area = 1;  // 当前格子的面积为1
  45.         
  46.         // 上
  47.         area += dfs(i - 1, j);
  48.         // 下
  49.         area += dfs(i + 1, j);
  50.         // 左
  51.         area += dfs(i, j - 1);
  52.         // 右
  53.         area += dfs(i, j + 1);
  54.         
  55.         return area;
  56.     }
  57. }
答案
  1. import java.util.Scanner;
  2.  
  3. class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scanner = new Scanner(System.in);
  6.         
  7.         // 读取矩阵的行数和列数
  8.         int N = scanner.nextInt();
  9.         int M = scanner.nextInt();
  10.         
  11.         int[][] grid = new int[N][M];
  12.         
  13.         // 读取矩阵
  14.         for (int i = 0; i < N; i++) {
  15.             for (int j = 0; j < M; j++) {
  16.                 grid[i][j] = scanner.nextInt();
  17.             }
  18.         }
  19.         
  20.         // 从边缘开始标记所有与边缘相连的陆地
  21.         for (int i = 0; i < N; i++) {
  22.             if (grid[i][0] == 1) {
  23.                 dfs(grid, i, 0, N, M);
  24.             }
  25.             if (grid[i][M - 1] == 1) {
  26.                 dfs(grid, i, M - 1, N, M);
  27.             }
  28.         }
  29.         for (int j = 0; j < M; j++) {
  30.             if (grid[0][j] == 1) {
  31.                 dfs(grid, 0, j, N, M);
  32.             }
  33.             if (grid[N - 1][j] == 1) {
  34.                 dfs(grid, N - 1, j, N, M);
  35.             }
  36.         }
  37.         
  38.         // 将所有未标记的陆地（孤岛）沉没
  39.         for (int i = 0; i < N; i++) {
  40.             for (int j = 0; j < M; j++) {
  41.                 if (grid[i][j] == 1) {
  42.                     grid[i][j] = 0;
  43.                 } else if (grid[i][j] == 2) {
  44.                     grid[i][j] = 1;
  45.                 }
  46.             }
  47.         }
  48.         
  49.         // 输出结果矩阵
  50.         for (int i = 0; i < N; i++) {
  51.             for (int j = 0; j < M; j++) {
  52.                 System.out.print(grid[i][j] + " ");
  53.             }
  54.             System.out.println();
  55.         }
  56.         
  57.         scanner.close();
  58.     }
  59.     
  60.     // 深度优先搜索（DFS）函数
  61.     private static void dfs(int[][] grid, int x, int y, int N, int M) {
  62.         if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] != 1) {
  63.             return;
  64.         }
  65.         grid[x][y] = 2; // 标记为非孤岛
  66.         dfs(grid, x + 1, y, N, M);
  67.         dfs(grid, x - 1, y, N, M);
  68.         dfs(grid, x, y + 1, N, M);
  69.         dfs(grid, x, y - 1, N, M);
  70.     }
  71. }
小结

先标记所有非孤岛，再沉没所有孤岛，再撤销所有非孤岛标记

103.水流问题

题目：103. 水流问题 (kamacoder.com)

思路：我需要找到最大的数字，然后再用dfs搜索？以每一个格子为中心，画一个十字，只要有朝向第一组边界和朝向第二组边界的递减数组即可，写一个函数，计算水流能否到达第一组边界，另一个函数计算水流能否到达第二组边界，两个函数返回均为true时，记录该坐标

尝试（超时）
  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3. class Main{
  4.     public static int N;
  5.     public static int M;
  6.     public static int[][] grid;
  7.     public static void main(String[] args){
  8.         Scanner scanner = new Scanner(System.in);
  9.         N = scanner.nextInt();
  10.         M = scanner.nextInt();
  11.         grid = new int[N][M];
  12.         ArrayList<int[]> dynamicArray = new ArrayList<>();
  13.         for(int i=0; i<N; i++){
  14.             for(int j=0; j<M; j++){
  15.                 grid[i][j] = scanner.nextInt();
  16.             }
  17.         }
  18.         
  19.         for(int i=0; i<N; i++){
  20.             for(int j=0; j<M; j++){
  21.                 if(firstBoundary(i,j) && secondBoundary(i,j)){
  22.                     dynamicArray.add(new int[]{i,j});
  23.                 }
  24.             }
  25.         }
  26.          // 输出动态数组中的内容
  27.         for (int[] array : dynamicArray) {
  28.             System.out.println(array[0] + " " + array[1]);
  29.         }
  30.         
  31.     }
  32.     public static boolean firstBoundary(int i,int j){
  33.         boolean up = true;
  34.         boolean left = true;
  35.         for(int k=i; k>0; k--){
  36.             if(grid[k][j]>grid[i][j]) up = false;
  37.         }
  38.         for(int k=j; k>0; k--){
  39.             if(grid[i][k]>grid[i][j]) left = false;
  40.         }
  41.         return up|| left;
  42.     }
  43.     public static boolean secondBoundary(int i,int j){
  44.         boolean down = true;
  45.         boolean right = true;
  46.         for(int k=i; k<N; k++){
  47.             if(grid[k][j]>grid[i][j]) down = false;
  48.         }
  49.         for(int k=j; k<M; k++){
  50.             if(grid[i][k]>grid[i][j]) right = false;
  51.         }
  52.         return down||right;
  53.     }
  54. }
答案
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. class Main {
  5.     public static int N;
  6.     public static int M;
  7.     public static int[][] grid;
  8.     public static boolean[][] canReachFirstBoundary;
  9.     public static boolean[][] canReachSecondBoundary;
  10.  
  11.     public static void main(String[] args) {
  12.         Scanner scanner = new Scanner(System.in);
  13.         N = scanner.nextInt();
  14.         M = scanner.nextInt();
  15.         grid = new int[N][M];
  16.         canReachFirstBoundary = new boolean[N][M];
  17.         canReachSecondBoundary = new boolean[N][M];
  18.  
  19.         for (int i = 0; i < N; i++) {
  20.             for (int j = 0; j < M; j++) {
  21.                 grid[i][j] = scanner.nextInt();
  22.             }
  23.         }
  24.  
  25.         // 从第一组边界开始反向DFS
  26.         for (int i = 0; i < N; i++) {
  27.             dfs(i, 0, canReachFirstBoundary);
  28.             dfs(i, M - 1, canReachSecondBoundary);
  29.         }
  30.         for (int j = 0; j < M; j++) {
  31.             dfs(0, j, canReachFirstBoundary);
  32.             dfs(N - 1, j, canReachSecondBoundary);
  33.         }
  34.  
  35.         // 找出既能到达第一组边界又能到达第二组边界的单元格
  36.         ArrayList<int[]> result = new ArrayList<>();
  37.         for (int i = 0; i < N; i++) {
  38.             for (int j = 0; j < M; j++) {
  39.                 if (canReachFirstBoundary[i][j] && canReachSecondBoundary[i][j]) {
  40.                     result.add(new int[]{i, j});
  41.                 }
  42.             }
  43.         }
  44.  
  45.         // 输出结果
  46.         for (int[] cell : result) {
  47.             System.out.println(cell[0] + " " + cell[1]);
  48.         }
  49.     }
  50.  
  51.     // 深度优先搜索（DFS）函数
  52.     private static void dfs(int x, int y, boolean[][] canReach) {
  53.         if (canReach[x][y]) {
  54.             return;
  55.         }
  56.         canReach[x][y] = true;
  57.  
  58.         int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  59.         for (int[] direction : directions) {
  60.             int newX = x + direction[0];
  61.             int newY = y + direction[1];
  62.             if (newX >= 0 && newX < N && newY >= 0 && newY < M && grid[newX][newY] >= grid[x][y]) {
  63.                 dfs(newX, newY, canReach);
  64.             }
  65.         }
  66.     }
  67. }
小结

反向dfs效率更高

104.建造最大岛屿

题目：104. 建造最大岛屿 (kamacoder.com)

思路：感觉肯定是要找到最大的岛屿，再去连接，或者是第二大的，又或者是岛屿从大到小，都试一遍，逐个将岛屿的某个边缘变为陆地

这个1 肯定是出现在岛屿的边缘，或许我可以先遍历一遍，找到所有的边缘，

尝试（写不出来）
  1. import java.util.Scanner;
  2.  
  3. class Main{
  4.     public static int N;
  5.     public static int M;
  6.     public static int[][] grid;
  7.     public static boolean[][] visited;
  8.     public static boolean flag;
  9.     public static void main(String[] args){
  10.         Scanner scan = new Scanner(System.in);
  11.         N = scan.nextInt();
  12.         M = scan.nextInt();
  13.         grid = new int[N][M];
  14.         for(int i=0; i<N; i++){
  15.             for(int j=0; j<M; j++){
  16.                 grid[i][j] = scan.nextInt();
  17.             }
  18.         }
  19.         
  20.         // 遍历grid，找到所有的边缘，单元格每与一个陆地接触，就加1
  21.         // 初始值为2，为了区分岛屿的1
  22.         for(int i=0; i<N; i++){
  23.             for(int j=0; j<M; j++){
  24.                 grid[i][j] = scan.nextInt();
  25.             }
  26.         }
  27.     }
  28.     public static void dfs(int i, int j){
  29.         if(i<0 || i>=N || j<0 ||  j>=M){
  30.             return;
  31.         }
  32.         visited[i][j] = true;
  33.         if(grid[i][j]==1) flag = true;
  34.         if(flag){
  35.             if(grid[i][j]==0){
  36.                 grid[i][j] =2;
  37.             }else{
  38.                 grid[i][j]+=1;
  39.             }
  40.         } 
  41.         dfs(i-1,j);
  42.         dfs(i+1,j);
  43.         dfs(i,j-1);
  44.         dfs(i,j+1);
  45.     }
  46.     
  47. }
答案(卡码网上别人的，看不懂)
  1. import java.util.Arrays;
  2. import java.util.Map;
  3. import java.util.Scanner;
  4.  
  5. // 逆向思维
  6. public class Main {
  7.     static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
  8.     static int ans = 0, area = 1;
  9.     static boolean[][] visited;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         int n = sc.nextInt(); // row
  13.         int m = sc.nextInt(); // col
  14.         int[][] graph = new int[n][m];
  15.  
  16.         for (int i = 0; i < n; i++) {
  17.             for (int j = 0; j < m; j++) {
  18.                 graph[i][j] = sc.nextInt();
  19.             }
  20.         }
  21.  
  22.  
  23.         boolean flag  = false;
  24.  
  25.         // 遍历
  26.         for (int i = 0; i < n; i++) {
  27.             for (int j = 0; j < m; j++) {
  28.                 area = 1;
  29.                 visited = new boolean[n][m];
  30.                 if (graph[i][j] == 0){
  31.                     dfs(i, j, graph, n, m);
  32.                     flag = true;
  33.  
  34.                 }
  35.             }
  36.         }
  37.  
  38.         System.out.println(flag ? ans : n * m);
  39.     }
  40.  
  41.     private static void dfs(int row, int col, int[][] graph, int n, int m) {
  42.         ans = Math.max(ans, area);
  43.         visited[row][col] = true;
  44.         for (int[] dir : dirs) {
  45.             int newX = dir[0] + row;
  46.             int newY = dir[1] + col;
  47.             if(newX >= 0 && newX < n && newY >= 0 && newY < m && graph[newX][newY] == 1 && !visited[newX][newY]){
  48.                 area++;
  49.                 dfs(newX,newY,graph,n,m);
  50.             }
  51.         }
  52.     }
  53.  
  54. }
答案（仿照代码随想录中C++的逻辑，运行错误）
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static int n, m;
  6.     static int count;
  7.     static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向
  8.  
  9.     public static void main(String[] args) {
  10.         Scanner scanner = new Scanner(System.in);
  11.         n = scanner.nextInt();
  12.         m = scanner.nextInt();
  13.         int[][] grid = new int[n][m];
  14.  
  15.         for (int i = 0; i < n; i++) {
  16.             for (int j = 0; j < m; j++) {
  17.                 grid[i][j] = scanner.nextInt();
  18.             }
  19.         }
  20.  
  21.         boolean[][] visited = new boolean[n][m]; // 标记访问过的点，初始化为false
  22.         Map<Integer, Integer> gridNum = new HashMap<>();
  23.         int mark = 2; // 记录每个岛屿的编号
  24.         boolean isAllGrid = true; // 标记是否整个地图都是陆地
  25.  
  26.         // 计算每个岛屿的面积并标记
  27.         for (int i = 0; i < n; i++) {
  28.             for (int j = 0; j < m; j++) {
  29.                 if (grid[i][j] == 0) isAllGrid = false;
  30.                 if (!visited[i][j] && grid[i][j] == 1) {
  31.                     count = 0;
  32.                     dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
  33.                     gridNum.put(mark, count); // 记录每一个岛屿的面积
  34.                     mark++; // 记录下一个岛屿编号
  35.                 }
  36.             }
  37.         }
  38.  
  39.         if (isAllGrid) {
  40.             System.out.println(n * m); // 如果都是陆地，返回全面积
  41.             return; // 结束程序
  42.         }
  43.  
  44.         // 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
  45.         int result = 0; // 记录最后结果
  46.         Set<Integer> visitedGrid = new HashSet<>(); // 标记访问过的岛屿
  47.  
  48.         for (int i = 0; i < n; i++) {
  49.             for (int j = 0; j < m; j++) {
  50.                 count = 1; // 记录连接之后的岛屿数量
  51.                 visitedGrid.clear(); // 每次使用时，清空
  52.                 if (grid[i][j] == 0) {
  53.                     for (int k = 0; k < 4; k++) {
  54.                         int neari = i + dir[k][0]; // 计算相邻坐标
  55.                         int nearj = j + dir[k][1];
  56.                         if (neari < 0 || nearj < 0 || neari >= n || nearj >= m) continue;
  57.                         if (visitedGrid.contains(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加
  58.                         // 把相邻四面的岛屿数量加起来
  59.                         count += gridNum.get(grid[neari][nearj]);
  60.                         visitedGrid.add(grid[neari][nearj]); // 标记该岛屿已经添加过
  61.                     }
  62.                 }
  63.                 result = Math.max(result, count);
  64.             }
  65.         }
  66.  
  67.         System.out.println(result);
  68.     }
  69.  
  70.     // 深度优先搜索函数
  71.     private static void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
  72.         if (visited[x][y] || grid[x][y] == 0) return; 
  73.         visited[x][y] = true; // 标记访问过
  74.         grid[x][y] = mark; // 给陆地标记新标签
  75.         count++;
  76.         for (int i = 0; i < 4; i++) {
  77.             int nextx = x + dir[i][0];
  78.             int nexty = y + dir[i][1];
  79.             if(nextx <0 || nextx >=n || nexty<0 || nexty >=m) continue;
  80.             dfs(grid, visited, nextx, nexty, mark);
  81.             
  82.         }
  83.     }
  84. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/804918
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号