Day58_20250206_图论part3_101.孤岛的总面积|102.沉没孤岛|103.水流问题|104.建造最大岛屿
Day58_20250206_图论part3_101.孤岛的总面积|102.沉没孤岛|103.水流问题|104.建造最大岛屿
101.孤岛的总面积
题目
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。
输出描述
输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。
输入示例
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出：0
思路
- 思路
- 主要思路：通过dfs和bfs将周边靠近陆地且相邻的陆地都变成海洋，然后去重新遍历地图统计此时还剩下的陆地。
- 周边陆地，将1变为0
- 代码
import java.util.*; public class Main { private static int count = 0;// 用于存储岛屿面积的全局变量 // 方向数组：表示四个方向（右、下、上、左） private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 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(); } } //step1:去除所有边界连接的岛屿 //1.遍历 左边界和右边界 for(int i=0;i<n;i++){ if(grid[i][0]==1) bfs(grid,i,0);//左 if(grid[i][m-1]==1) bfs(grid,i,m-1);//右 } // 2. 遍历 上边界和下边界 for(int j=0;j<m;j++){ if(grid[0][j]==1) bfs(grid,0,j);//上 if(grid[n-1][j]==1) bfs(grid,n-1,j);//下 } //step2:计算所有孤岛的总面积 count = 0; // 重置计数器 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { // 遇到新的孤岛 bfs(grid, i, j); // 计算该孤岛的面积 } } } System.out.println(count); } public static void bfs(int[][] grid, int x, int y) { //step1:新建队列 Queue<int[]> queue=new LinkedList<>(); queue.add(new int[]{x, y}); // 将起点加入队列 grid[x][y] = 0; // 只要加入队列，立刻标记为水，防止重复访问 count++; // 计数+1（当前岛屿的第一个陆地） //step2:遍历 while (!queue.isEmpty()) { int[] cur = queue.poll(); // 取出队列头部的坐标 int curX = cur[0], 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 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue; // 如果是陆地（1），加入队列，并标记为水（0） if(grid[nextX][nextY]==1){ queue.add(new int[]{nextX,nextY}); count++;//计数+1，表示该陆地属于同一个岛屿 grid[nextX][nextY]=0;//立刻标记，防止重复访问 } } } } }
总结
102.沉没孤岛
题目
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。
之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出将孤岛“沉没”之后的岛屿矩阵。
输入示例：
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例：
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1
思路
- 思路
- 【周边标记，区分边缘陆地和中间陆地】深搜或广搜将地图周边的1(陆地)全部改成2(特殊标记)
- 【沉没】将水域中间1(陆地)全部改成水域(0)
- 【修改符号】将之前标记的2改为1(陆地)
- 代码
-
import java.util.Scanner; public class Main{ static int[][] dir={{-1,0},{0,-1},{1,0},{0,1}}; 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);//左边界的岛屿 if(grid[i][m-1]==1) dfs(grid,i,m-1);//右边界的岛屿 } //遍历上下边界 for(int j=0;j<m;j++){ if(grid[0][j]==1) dfs(grid,0,j);//上边界的岛屿 if(grid[n-1][j]==1) dfs(grid,n-1,j);//下边界的岛屿 } //步骤2和步骤3 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]==1) grid[i][j]=0;//将中间陆地1全部改为水域0 if(grid[i][j]==2) grid[i][j]=1;//将之前标记的2改为1陆地 } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ System.out.println(grid[i][j]+" ");//空格 } System.out.println();//换行 } scanner.close(); } public static void dfs(int[][] grid,int x, int y){ grid[x][y]=2;//周边陆地标记为2 for(int[] d:dir){ int nextX=x+d[0]; int nextY=y+d[1]; //超过边界,继续，不遍历 if(nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[0].length){ continue; } //不符合条件，不继续遍历[水或已经变为2] if(grid[nextX][nextY]==0||grid[nextX][nextY]==2) continue; dfs(grid,nextX,nextY); } } }
-
总结
- 细节比较多，明天再复习一遍
103.水流问题
题目
题目描述：
现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。
输入描述：
第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。
后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。
输出描述：
输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。
输入示例：
5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1
输出示例：
0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1
思路
- 思路
- 遍历每个点，看这个点能不能同时到达第一组边界和第二组边界。
- dfs和bfs
- 优化思路
- 从第一组边界上的节点逆流而上，将遍历过的节点都标记上。
- 从第二组边界的边上节点逆流而上，将遍历过的节点也标记上。
- 两边都标记过的节点是既可以流太平洋也可以流大西洋的节点。
- 代码
-
import java.util.*; public class Main { // 采用 DFS 进行搜索 public static void dfs(int[][] heights, int x, int y, boolean[][] visited, int preH) { // 遇到边界或者访问过的点，直接返回 if (x < 0 || x >= heights.length || y < 0 || y >= heights[0].length || visited[x][y]) return; // 不满足水流入条件的直接返回 if (heights[x][y] < preH) return; // 满足条件，设置为true，表示可以从边界到达此位置 visited[x][y] = true; // 向下一层继续搜索 dfs(heights, x + 1, y, visited, heights[x][y]); dfs(heights, x - 1, y, visited, heights[x][y]); dfs(heights, x, y + 1, visited, heights[x][y]); dfs(heights, x, y - 1, visited, heights[x][y]); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] heights = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { heights[i][j] = sc.nextInt(); } } // 初始化两个二位boolean数组，代表两个边界 boolean[][] pacific = new boolean[m][n]; boolean[][] atlantic = new boolean[m][n]; // 从左右边界出发进行DFS for (int i = 0; i < m; i++) { dfs(heights, i, 0, pacific, Integer.MIN_VALUE); dfs(heights, i, n - 1, atlantic, Integer.MIN_VALUE); } // 从上下边界出发进行DFS for (int j = 0; j < n; j++) { dfs(heights, 0, j, pacific, Integer.MIN_VALUE); dfs(heights, m - 1, j, atlantic, Integer.MIN_VALUE); } // 当两个边界二维数组在某个位置都为true时，符合题目要求 List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pacific[i][j] && atlantic[i][j]) { res.add(Arrays.asList(i, j)); } } } // 打印结果 for (List<Integer> list : res) { for (int k = 0; k < list.size(); k++) { if (k == 0) { System.out.print(list.get(k) + " "); } else { System.out.print(list.get(k)); } } System.out.println(); } } }
-
总结
104.建造最大岛屿
题目
题目描述：
给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。
岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。
输入描述：
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述：
输出一个整数，表示最大的岛屿面积。
输入示例：
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出示例
6
思路
- 思路
- 暴力想法：
- 遍历地图尝试将每一个0改成1，搜索地图中的最大的岛屿面积。
- 遍历地图+深搜岛屿，时间复杂度为n*n
- 每改变一个0的方格，都需要重新计算一个地图的最大面积，整体时间复杂度为n^4。
- 优化：
- 只要用1次深搜把每个岛屿的面积记录下来就好。
- 1.【计算各个岛屿面积】一次遍历地图，得出各个岛屿的面积，并做编号记录，可以使用map记录，key为岛屿编号，value为岛屿面积。
- 2.【0变1后的各个岛屿面积】再遍历地图，遍历0的方格(0变为1)，统计该1(由0变的1)周边岛屿面积，将其相邻面积相加在一起。
- 3.【求最大面积】遍历所有0之后，选一个0变成1之后的最大面积。
- 暴力想法：
- 代码
import java.util.*; public class Main{ //global static int count;//计数岛屿的面积 static int mark;//标记岛屿 static int[][] dirs={{0,1},{0,-1},{1,0},{0,-1}};//方位 public static void main(String[] args){ //接收输入 Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int[][] grid=new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ grid[i][j]=sc.nextInt(); } } mark=2; boolean[][] visited=new boolean[m][n];//visited //HashMap 记录某片岛屿的标记号和面积 HashMap<Integer,Integer> getSize=new HashMap<>(); //HashSet 判断某一位置水四周是否存在不同标记编号的岛屿 HashSet<Integer> set=new HashSet<>(); //boolean，dfs之后是否全是岛屿？？ boolean isAllIsland=true; //1.计算每个岛屿面积：遍历二维数组进行dfs,标记每片岛屿的编号，记录对应的面积 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==0) isAllIsland=false; if(grid[i][j]==1){ count=0; dfs(grid,visited,i,j); getSize.put(mark,count); mark++; } } } int result=0; if(isAllIsland) result=m*n; //对标记完的grid继续遍历，判断每个水位置是否有岛屿，并记录下四周不同相邻岛屿的面积之和 //每次计算完一个水位置周围可能存在的岛屿面积之和，更新result变量 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ //遇到水，清空数 set.clear(); //当前水位置变更为岛屿，初始化为1？？ int curSize=1; for(int[] dir:dirs){ int nextX=i+dir[0]; int nextY=j+dir[1]; //越界跳过 if(nextX<0||nextX>=m||nextY<0||nextY>=n){continue;} //当前标记 int curMark=grid[nextX][nextY]; //if[当前相邻的岛屿已经遍历过][HashMap不存在这个编号]，继续搜索 if(set.contains(curMark)||!getSize.containsKey(curMark)) continue; set.add(curMark); curSize+=getSize.get(curMark); } result=Math.max(result,curSize); } } System.out.println(result); } public static void dfs(int[][] grid,boolean[][] visited,int x,int y){ //遇到边界,直接return if(x<0||x>=grid.length||y<0||y>=grid[0].length) return; //遇到已经访问过的或者遇到海水，直接返回 if(visited[x][y]||grid[x][y]==0) return; visited[x][y]=true; count++; grid[x][y]=mark; //继续向下层搜索[上下左右] dfs(grid,visited,x,y+1); dfs(grid,visited,x,y-1); dfs(grid,visited,x+1,y); dfs(grid,visited,x-1,y); } }
总结
- 细节比较多，还需要再多复习