代码随想录算法训练营第五十七天 | 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题 104.建造最大岛屿
101. 孤岛的总面积
题目链接：KamaCoder
文档讲解：代码随想录
状态：AC
Java代码：
import java.util.*;class Main {static int count = 0;static int res = 0;static boolean island = true;public static int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] arr = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = scan.nextInt();}}scan.close();boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j] == 1 && !visited[i][j]) {visited[i][j] = true;count++;dfs(arr, visited, i, j);if (island) {res += count;}island = true;count = 0;}}}System.out.println(res);}public static void dfs(int[][] arr, boolean[][] visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length) {island = false;continue;}if (arr[nextX][nextY] == 1 && !visited[nextX][nextY]) {visited[nextX][nextY] = true;count++;dfs(arr, visited, nextX, nextY);}}}
}
102. 沉没孤岛
题目链接：KamaCoder
文档讲解：代码随想录
状态：AC
Java代码：
import java.util.*;class Main {public static int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};public static void dfs(int[][] arr, int x, int y) {arr[x][y] = 2;for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length) {continue;}if (arr[nextX][nextY] == 1) {dfs(arr, nextX, nextY);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] arr = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = scan.nextInt();}}scan.close();for (int i = 0; i < n; i++) {if (arr[i][0] == 1) {dfs(arr, i, 0);}if (arr[i][m - 1] == 1) {dfs(arr, i, m - 1);}}for (int i = 0; i < m; i++) {if (arr[0][i] == 1) {dfs(arr, 0, i);}if (arr[n - 1][i] == 1) {dfs(arr, n - 1, i);}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j] == 1) {arr[i][j] = 0;} else if (arr[i][j] == 2) {arr[i][j] = 1;}System.out.print(arr[i][j]);if (j == m - 1) {System.out.print("\n");} else {System.out.print(" ");}}}}
}
103. 水流问题
题目链接：KamaCoder
文档讲解：代码随想录
状态：AC
Java代码：
import java.util.*;class Main {public static int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};public static void dfs(int[][] arr, boolean[][] visited, int x, int y, int height) {// 如果已访问，直接返回if (visited[x][y]) {return;}// 标记当前节点为已访问visited[x][y] = true;// 向四个方向深度优先搜索for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];// 只访问高度 >= 当前高度的位置，保证水可以继续流动if (nextX >= 0 && nextY >= 0 && nextX < arr.length && nextY < arr[0].length&& arr[nextX][nextY] >= height) {dfs(arr, visited, nextX, nextY, arr[nextX][nextY]);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] arr = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = scan.nextInt();}}scan.close();boolean[][] first = new boolean[n][m];boolean[][] second = new boolean[n][m];for (int i = 0; i < n; i++) {dfs(arr, first, i, 0, arr[i][0]);dfs(arr, second, i, m - 1, arr[i][m - 1]);}for (int i = 0; i < m; i++) {dfs(arr, first, 0, i, arr[0][i]);dfs(arr, second, n - 1, i, arr[n - 1][i]);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (first[i][j] && second[i][j]) {System.out.println(i + " " + j);}}}}
}104.建造最大岛屿
题目链接：KamaCoder
文档讲解：代码随想录
状态：AC
Java代码：
import java.util.*;class Main {public static int count = 0;public static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};public static void dfs(int[][] arr, boolean[][] visited, int x, int y, int mark) {for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length || visited[nextX][nextY]) {continue;}if (arr[nextX][nextY] == 1) {count++;arr[nextX][nextY] = mark;visited[nextX][nextY] = true;dfs(arr, visited, nextX, nextY, mark);}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[][] arr = new int[n][m];boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = scan.nextInt();}}scan.close();Map<Integer, Integer> map = new HashMap<>();int mark = 2;boolean isAll = true;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j] == 0) {isAll = false;}if (arr[i][j] == 1 && !visited[i][j]) {arr[i][j] = mark;visited[i][j] = true;count++;dfs(arr, visited, i, j, mark);map.put(mark, count);count = 0;mark++;}}}if (isAll) {System.out.println(m * n);return;}int value = 0;int res = 0;Set<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j] == 0) {set.clear();value = 0;for (int z = 0; z < 4; z++) {int nextX = i + dir[z][0];int nextY = j + dir[z][1];if (nextX < 0 || nextY < 0 || nextX >= arr.length || nextY >= arr[0].length) {continue;}if (map.containsKey(arr[nextX][nextY]) && !set.contains(arr[nextX][nextY])) {set.add(arr[nextX][nextY]);value += map.get(arr[nextX][nextY]);}}res = Math.max(res, value);}}}System.out.println(res + 1);}
}