代码随想录算法训练营Day57 | 卡玛网 101.孤岛的总面积、卡玛网 102.沉没孤岛、卡玛网 103. 水流问题、卡玛网 104.建造最大岛屿
目录
卡玛网 101.孤岛的总面积
卡玛网 102.沉没孤岛
卡玛网 103. 水流问题
卡玛网 104.建造最大岛屿
卡玛网 101.孤岛的总面积
题目
101. 孤岛的总面积
思路
代码随想录：101.孤岛的总面积
重点： 首先遍历图的四条边，把其中的陆地及其位于的岛屿都记录为 0，然后再遍历整张地图，并开始计算面积。
题解
DFS：
import java.util.*;public class Main {private static final int[][] DIR = {{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[][] graph = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {graph[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if ((i == 0 || j == 0 || i == N - 1 || j == M - 1) && graph[i][j] == 1)dfs(graph, i, j, N, M);}}int totalArea = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 1)totalArea += dfs(graph, i, j, N, M);}}System.out.println(totalArea);}private static int dfs(int[][] graph, int x, int y, int N, int M) {if (x < 0 || y < 0 || x >= N || y >= M || graph[x][y] != 1)return 0;graph[x][y] = 0;int area = 1;for (int i = 0; i < 4; i++) {int nextX = x + DIR[i][0];int nextY = y + DIR[i][1];area += dfs(graph, nextX, nextY, N, M);}return area;}
}
BFS：
import java.util.*;public class Main {private static final int[][] DIR = {{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[][] graph = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {graph[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if ((i == 0 || j == 0 || i == N - 1 || j == M - 1) && graph[i][j] == 1)bfs(graph, i, j, N, M);}}int totalArea = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 1)totalArea += bfs(graph, i, j, N, M);}}System.out.println(totalArea);}private static int bfs(int[][] graph, int x, int y, int N, int M) {Deque<int[]> deque = new LinkedList<>();deque.offer(new int[]{x, y});graph[x][y] = 0;int area = 1;while (!deque.isEmpty()) {int[] cur = deque.poll();int curX = cur[0];int curY = cur[1];for (int i = 0; i < 4; i++) {int nextX = curX + DIR[i][0];int nextY = curY + DIR[i][1];if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M || graph[nextX][nextY] != 1)continue;graph[nextX][nextY] = 0;area++;deque.offer(new int[]{nextX, nextY});}}return area;}
}
卡玛网 102.沉没孤岛
题目
102. 沉没孤岛
思路
代码随想录：102.沉没孤岛
题解
DFS：
import java.util.*;public class Main {private static final int[][] DIR = {{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[][] graph = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {graph[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if ((i == 0 || j == 0 || i == N - 1 || j == M - 1) && graph[i][j] == 1)dfs(graph, i, j, N, M);}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 2) {System.out.print(1 + " ");} else {System.out.print(0 + " ");}}System.out.println();}}private static void dfs(int[][] graph, int x, int y, int N, int M) {if (x < 0 || y < 0 || x >= N || y >= M || graph[x][y] != 1)return;graph[x][y] = 2;for (int i = 0; i < 4; i++) {int nextX = x + DIR[i][0];int nextY = y + DIR[i][1];dfs(graph, nextX, nextY, N, M);}}
}
BFS：
import java.util.*;public class Main {private static final int[][] DIR = {{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[][] graph = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {graph[i][j] = sc.nextInt();}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if ((i == 0 || j == 0 || i == N - 1 || j == M - 1) && graph[i][j] == 1)bfs(graph, i, j, N, M);}}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (graph[i][j] == 2) {System.out.print(1 + " ");} else {System.out.print(0 + " ");}}System.out.println();}}private static void bfs(int[][] graph, int x, int y, int N, int M) {Deque<int[]> deque = new LinkedList<>();deque.offer(new int[]{x, y});graph[x][y] = 2;while (!deque.isEmpty()) {int[] cur = deque.poll();int curX = cur[0];int curY = cur[1];for (int i = 0; i < 4; i++) {int nextX = curX + DIR[i][0];int nextY = curY + DIR[i][1];if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M || graph[nextX][nextY] != 1)continue;graph[nextX][nextY] = 2;deque.offer(new int[]{nextX, nextY});}}}
}
卡玛网 103. 水流问题
题目
103. 水流问题
思路
代码随想录：103.水流问题
初步思路是遍历图中的所有点，判断是否能同时到达第一边界和第二边界，时间复杂度为 O(N2 * M2)，超时。
优化方案：逆向思维，分别从第一边界和第二边界逆流而上，将能到达的节点进行标记，最后两边都标记了的节点就是目标节点。
题解
DFS：
import java.util.*;public class Main {private static final int[][] DIR = {{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[][] graph = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {graph[i][j] = sc.nextInt();}}boolean[][] firstVisited = new boolean[N][M];boolean[][] secondVisited = new boolean[N][M];for (int i = 0; i < N; i++) {dfs(graph, i, 0, firstVisited);//从左边界开始dfs(graph, i, M - 1, secondVisited);//从右边界开始}for (int j = 0; j < M; j++) {dfs(graph, 0, j, firstVisited);//从上边界开始dfs(graph, N - 1, j, secondVisited);//从下边界开始}for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (firstVisited[i][j] && secondVisited[i][j]) {System.out.print(i + " ");System.out.println(j);}}}}private static void dfs(int[][] graph, int x, int y, boolean[][] visited) {if (x < 0 || y < 0 || x >= graph.length || y >= graph[0].length || 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 >= graph.length || nextY >= graph[0].length || visited[nextX][nextY] || graph[nextX][nextY] < graph[x][y])continue;dfs(graph, nextX, nextY, visited);}}
}
卡玛网 104.建造最大岛屿
题目
104. 建造最大岛屿
思路
代码随想录：104.建造最大岛屿
- 第一次遍历地图，得出各个岛屿的面积，并做独立的编号，记录在HashMap中，key 为岛屿编号，value 为岛屿面积。
- 第二次遍历地图，遍历为 0 的方格，将其变为 1，并统计该方格周边的岛屿面积，将其相邻面积加在一起，得到新建的岛屿面积。
- 遍历所有 0 之后，可以得到最大面积。
题解
import java.util.*;public class Main {// 定义四个方向static int[][] DIR = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};static int mark = 2; // 标记岛屿编号，初始值为2（0代表水，1代表未标记的岛屿）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> islandSizeMap = new HashMap<>();//判断是否全为陆地boolean isAllIsland = true;// 标记每片岛屿并记录面积for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 0) {isAllIsland = false;} else if (grid[i][j] == 1) {int currentArea = dfs(grid, i, j);islandSizeMap.put(mark, currentArea);mark++;}}}//如果全为陆地，直接返回总面积int result = isAllIsland ? N * M : 0;// 遍历每个水格子，计算可能的最大岛屿面积for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 0) {HashSet<Integer> set = new HashSet<>();int newArea = 1;// 计算周围的不同岛屿面积之和for (int[] dir : DIR) {int newX = i + dir[0];int newY = j + dir[1];if (newX < 0 || newX >= N || newY < 0 || newY >= M) {continue;}int currentMark = grid[newX][newY];if (currentMark > 1 && !set.contains(currentMark)) {set.add(currentMark);newArea += islandSizeMap.get(currentMark);}}result = Math.max(result, newArea);}}}System.out.println(result);}// DFSprivate static int dfs(int[][] grid, int x, int y) {if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {return 0;}grid[x][y] = mark;int area = 1;for (int[] dir : DIR) {area += dfs(grid, x + dir[0], y + dir[1]);}return area;}
}