网站维护模板,网站建设与运营的预算方案模板,php商城网站开发实例视频教程,乐清有那些网站目录
卡玛网 101.孤岛的总面积
卡玛网 102.沉没孤岛
卡玛网 103. 水流问题
卡玛网 104.建造最大岛屿
卡玛网 101.孤岛的总面积
题目
101. 孤岛的总面积
思路
代码随想录#xff1a;101.孤岛的总面积
重点#xff1a; 首先遍历图的四条边#xff0c;把其中的陆地及…目录
卡玛网 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) {Dequeint[] 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) {Dequeint[] 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; // 标记岛屿编号初始值为20代表水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();}}//记录岛屿编号以及面积HashMapInteger, 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) {HashSetInteger 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;}
}
