代码随想录算法训练营第五十七天 | 101. 孤岛的总面积 102. 沉没孤岛 103. 水流问题 104.建造最大岛屿

101 孤岛的总面积

题目链接：

文档讲解： 状态：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 沉没孤岛

题目链接：

文档讲解： 状态：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 水流问题

题目链接：

文档讲解： 状态：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.建造最大岛屿

题目链接：

文档讲解： 状态：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 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 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); } }