代码随想录Day66（图论Part03）

101.孤岛的总面积

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

思路：无

答案

import java.util.Scanner;class Main {private static int N, M;private static int[][] grid;private static boolean[][] visited;private static boolean touchesEdge;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);N = scanner.nextInt();M = scanner.nextInt();grid = new int[N][M];visited = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {grid[i][j] = scanner.nextInt();}}int totalIslandArea = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 1 && !visited[i][j]) {touchesEdge = false;int islandArea = dfs(i, j);if (!touchesEdge) {totalIslandArea += islandArea;}}}}System.out.println(totalIslandArea);}private static int dfs(int x, int y) {if (x < 0 || x >= N || y < 0 || y >= M) {return 0;}if (grid[x][y] == 0 || visited[x][y]) {return 0;}if (x == 0 || x == N - 1 || y == 0 || y == M - 1) {touchesEdge = true;}visited[x][y] = true;int area = 1;area += dfs(x + 1, y);area += dfs(x - 1, y);area += dfs(x, y + 1);area += dfs(x, y - 1);return area;}
}

小结

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

102.沉没孤岛

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

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

尝试（标题4）

import java.util.Scanner;class Main{public static int m;public static int n;public static int[][] grid;public static boolean[][] visited;public static void main(String[] args){Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();grid = new int[n][m];visited = new boolean[n][m];for(int i=0; i<n; i++){for(int j=0; j<m; j++){grid[i][j] = scanner.nextInt();}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1 && !visited[i][j]) {int area = dfs(i, j);if(area == 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();}}private static int dfs(int i, int j) {if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0 || visited[i][j]) {return 0;}visited[i][j] = true;int area = 1;  // 当前格子的面积为1// 上area += dfs(i - 1, j);// 下area += dfs(i + 1, j);// 左area += dfs(i, j - 1);// 右area += dfs(i, j + 1);return area;}
}

答案

import java.util.Scanner;class Main {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();}}// 从边缘开始标记所有与边缘相连的陆地for (int i = 0; i < N; i++) {if (grid[i][0] == 1) {dfs(grid, i, 0, N, M);}if (grid[i][M - 1] == 1) {dfs(grid, i, M - 1, N, M);}}for (int j = 0; j < M; j++) {if (grid[0][j] == 1) {dfs(grid, 0, j, N, M);}if (grid[N - 1][j] == 1) {dfs(grid, N - 1, j, N, M);}}// 将所有未标记的陆地（孤岛）沉没for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 1) {grid[i][j] = 0;} else 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();}scanner.close();}// 深度优先搜索（DFS）函数private static void dfs(int[][] grid, int x, int y, int N, int M) {if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] != 1) {return;}grid[x][y] = 2; // 标记为非孤岛dfs(grid, x + 1, y, N, M);dfs(grid, x - 1, y, N, M);dfs(grid, x, y + 1, N, M);dfs(grid, x, y - 1, N, M);}
}

小结

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

103.水流问题

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

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

尝试（超时）

import java.util.Scanner;
import java.util.ArrayList;
class Main{public static int N;public static int M;public static int[][] grid;public static void main(String[] args){Scanner scanner = new Scanner(System.in);N = scanner.nextInt();M = scanner.nextInt();grid = new int[N][M];ArrayList<int[]> dynamicArray = new ArrayList<>();for(int i=0; i<N; i++){for(int j=0; j<M; j++){grid[i][j] = scanner.nextInt();}}for(int i=0; i<N; i++){for(int j=0; j<M; j++){if(firstBoundary(i,j) && secondBoundary(i,j)){dynamicArray.add(new int[]{i,j});}}}// 输出动态数组中的内容for (int[] array : dynamicArray) {System.out.println(array[0] + " " + array[1]);}}public static boolean firstBoundary(int i,int j){boolean up = true;boolean left = true;for(int k=i; k>0; k--){if(grid[k][j]>grid[i][j]) up = false;}for(int k=j; k>0; k--){if(grid[i][k]>grid[i][j]) left = false;}return up|| left;}public static boolean secondBoundary(int i,int j){boolean down = true;boolean right = true;for(int k=i; k<N; k++){if(grid[k][j]>grid[i][j]) down = false;}for(int k=j; k<M; k++){if(grid[i][k]>grid[i][j]) right = false;}return down||right;}
}

答案

import java.util.ArrayList;
import java.util.Scanner;class Main {public static int N;public static int M;public static int[][] grid;public static boolean[][] canReachFirstBoundary;public static boolean[][] canReachSecondBoundary;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);N = scanner.nextInt();M = scanner.nextInt();grid = new int[N][M];canReachFirstBoundary = new boolean[N][M];canReachSecondBoundary = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {grid[i][j] = scanner.nextInt();}}// 从第一组边界开始反向DFSfor (int i = 0; i < N; i++) {dfs(i, 0, canReachFirstBoundary);dfs(i, M - 1, canReachSecondBoundary);}for (int j = 0; j < M; j++) {dfs(0, j, canReachFirstBoundary);dfs(N - 1, j, canReachSecondBoundary);}// 找出既能到达第一组边界又能到达第二组边界的单元格ArrayList<int[]> result = new ArrayList<>();for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (canReachFirstBoundary[i][j] && canReachSecondBoundary[i][j]) {result.add(new int[]{i, j});}}}// 输出结果for (int[] cell : result) {System.out.println(cell[0] + " " + cell[1]);}}// 深度优先搜索（DFS）函数private static void dfs(int x, int y, boolean[][] canReach) {if (canReach[x][y]) {return;}canReach[x][y] = true;int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (int[] direction : directions) {int newX = x + direction[0];int newY = y + direction[1];if (newX >= 0 && newX < N && newY >= 0 && newY < M && grid[newX][newY] >= grid[x][y]) {dfs(newX, newY, canReach);}}}
}