网页制作实战视频_品牌_北京网聘咨询有限公司_企业员工培训内容及计划

Day57_20250205_图论part3_99.岛屿数量深搜|99.岛屿数量广搜|100.岛屿的最大面积

99.岛屿数量深搜【深搜2种写法，区别】

题目 ·

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

思路

问题
- 什么情况下是岛屿？
  - 如果陆地1在左边界，其上下右是0代表被包围(斜角不算)。
    - 同理，右边界是上下左，上边界是左右下，下边界是左右上。
  - 如果陆地1不在边界，上下左右都被包围。
  - 如果一个岛屿由多个陆地1组成，需要深搜到不能再搜索时，再计算岛屿数量
- 我的思路
  - 深搜的本质是不撞南墙不回头，“南墙”是水0，同时上下左右的边界各多加一层0，约束边界情况。
  - 深搜三部曲
    - 确定递归函数和参数
      - graph,始,末
    - 确定终止条件并收获结果
      - 当搜到x==边界时，存放结果
    - 处理目前搜索节点出发的路径
      - 处理节点，如果满足条件【边界都是0】，加入到单一路径中，
      - 递归
      - 回溯
思路
- 水平方向/竖直向上相邻的陆地连接而成
- 遇到一个没有遍历过的陆地，计数器就加1，将所有陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过，计数器是最终岛屿的数量。
- 怎么标记？使用DFS，BFS或查集。

代码

import java.util.Scanner;public class Main{public static int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};public static void main(String[] args){//输入Scanner sc=new Scanner(System.in);//m个节点，n条边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();}}boolean[][] visited=new boolean[m][n];int ans=0;for(int i=0;i<m;i++){//只对新发现的岛屿进行dfsfor(int j=0;j<n;j++){//如果发现新的岛屿[陆地没被访问过&&当前位置是陆地]if(!visited[i][j]&&grid[i][j]==1){ans++;visited[i][j]=true;dfs(visited,i,j,grid);}}}System.out.println(ans);}public static void dfs(boolean[][] visited,int x,int y,int[][] grid){//遍历方向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>=grid.length||nextY>=grid[0].length){continue;}//终止条件[未被访问过and遇到陆地] 扩展岛屿，只扩展到未访问的陆地，避免重复访问if(!visited[nextX][nextY]&&grid[nextX][nextY]==1){visited[nextX][nextY]=true;dfs(visited,nextX,nextY,grid);}}}}

代码2

import java.util.Scanner;public class Main {public static int[][] dir = {{0, 1}, {1, 0}, {-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();}}boolean[][] visited = new boolean[m][n];int ans = 0;// 遍历整个网格，查找新的岛屿for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) { // 遇到未访问的陆地ans++; // 发现新岛屿dfs(visited, grid, i, j); // 进行 DFS 遍历}}}System.out.println(ans);}public static void dfs(boolean[][] visited, int[][] grid, int x, int y) {// **终止条件**if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || visited[x][y] || grid[x][y] == 0) {return;}visited[x][y] = true; // 标记当前陆地为已访问// 遍历四个方向for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];dfs(visited, grid, nextX, nextY); // 递归探索}}
}

总结

注意有两个if判断条件相似，避免混淆
- 扩展岛屿，只扩展到未访问的陆地
  - //终止条件[未被访问过and遇到陆地] 扩展岛屿，只扩展到未访问的陆地，避免重复访问
    if(!visited[nextX][nextY]&&grid[nextX][nextY]==1)
- 只对新发现的岛屿进行dfs
  - /如果发现新的岛屿[陆地没被访问过&&当前位置是陆地]
    if(!visited[i][j]&&grid[i][j]==1){
暂时掌握思路了，但是不能独立敲一遍代码，一刷先掌握思路。
2种写法
- 法1，只扩展到未访问的陆地，避免重复访问。
- 法2，不管节点是否合法，先dfs,最后在终止条件的地方进行判断，不合法再return。

99.岛屿数量广搜【广搜的两种写法，bfs,】

题目

代码随想录

题目描述：

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例：

输出示例：

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

1 <= N, M <= 50

思路

细节
- 注意，加入队列就代表走过，需要标记，而不是从队列拿出来的时候再去标记走过。

代码

import java.util.*;public class Main{public static int[][] dir={{0,1},{1,0},{0,-1},{-1,0}};//下右上左逆时针遍历                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 };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];boolean[][] visited=new boolean[m][n];int ans=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){grid[i][j]=sc.nextInt();}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!visited[i][j]&&grid[i][j]==1){ans++;bfs(visited,i,j,grid);}}}System.out.println(ans);}public static void bfs(boolean[][] visited,int x,int y,int[][] grid){//存储需要遍历的节点，存储位置Queue<AbstractMap.SimpleEntry<Integer, Integer>> queue = new LinkedList<>();//将起始坐标(x,y)加入队列，queue.add(new AbstractMap.SimpleEntry<>(x, y));visited[x][y]=true;//遇到入队直接标记为优先，避免重复访问while(!queue.isEmpty()){AbstractMap.SimpleEntry<Integer, Integer> cur = queue.poll(); // 取出队列中的坐标//记录坐标，当前处理的坐标int curX = cur.getKey();int curY = cur.getValue();for(int i=0;i<4;i++){//顺时针遍历新节点next，下面记录坐标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;}if(!visited[nextX][nextY]&&grid[nextX][nextY]==1){queue.add(new AbstractMap.SimpleEntry<>(nextX, nextY));visited[nextX][nextY]=true;//逻辑同上}}}}
}

总结

写不出来

100.岛屿的最大面积

题目

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

输入示例

输出示例：4

思路

思路
- 法1，dfs只处理下一个节点，即在主函数遇到岛屿后计数+1,dfs处理接下来的相邻陆地。
- 法2，dfs处理当前节点，即在主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地。

代码

dfs
- 法1，DFS处理下一个节点(处理接下来的相邻陆地)
  - 主函数先计数+1，然后DFS递归处理剩余相邻陆地
  - 计数count初始值+1,DFS遇到新陆地时count++
  - DFS仅处理下一个节点
- 法2，DFS处理当前节点(处理接下来的全部陆地)
  - 主函数不计数，而是在DFS内部计数
  - count初始值0,DFS内遇到陆地时count++
  - DFS处理当前节点，然后递归处理相邻节点

dfs法1

import java.util.*;public class Main {static int count; // 记录当前岛屿的面积static 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[][] grid = new int[n][m];boolean[][] visited = new boolean[n][m];//邻接矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}int maxArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {//遇到新发现的陆地时if (!visited[i][j] && grid[i][j] == 1) {count = 1; // 计数从 1 开始（因为主函数先发现这个点）visited[i][j] = true;dfs(grid, visited, i, j);maxArea = Math.max(maxArea, count);}}}System.out.println(maxArea);}public static void dfs(int[][] grid, 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 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue; // 越界检查if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) { // 没访问过的陆地visited[nextX][nextY] = true;count++; // 遇到新陆地，面积 +1dfs(grid, visited, nextX, nextY);}}}}

dfs法2

import java.util.*;public class Main {static int count;static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右、下、左、上public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：已访问 or 遇到水visited[x][y] = true;count++; // 当前节点属于岛屿，计数+1for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue; // 越界检查dfs(grid, visited, nextX, nextY);}}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];boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}int maxArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 0; // 计数初始值 0，在 DFS 内部计数dfs(grid, visited, i, j);maxArea = Math.max(maxArea, count);}}}System.out.println(maxArea);}
}

bfs

import java.util.*;public class Main {static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右、下、左、上public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] map = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = scanner.nextInt();}}boolean[][] visited = new boolean[n][m];int maxArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && map[i][j] == 1) {//求最大面积maxArea = Math.max(maxArea, bfs(map, visited, i, j));}}}System.out.println(maxArea);}static int bfs(int[][] map, boolean[][] visited, int x, int y) {Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{x, y});visited[x][y] = true;int area = 0; // 记录当前岛屿面积while (!queue.isEmpty()) {int[] node = queue.poll();int curX = node[0], curY = node[1];area++; // 统计岛屿面积for (int[] d : dir) {int nextX = curX + d[0],；int nextY = curY + d[1];if (nextX >= 0 && nextX < map.length && nextY >= 0 && nextY < map[0].length && !visited[nextX][nextY] && map[nextX][nextY] == 1) {queue.add(new int[]{nextX, nextY});visited[nextX][nextY] = true;}}}return area;}
}

网页制作实战视频_品牌_北京网聘咨询有限公司_企业员工培训内容及计划

Day57_20250205_图论part3_99.岛屿数量深搜|99.岛屿数量广搜|100.岛屿的最大面积

99.岛屿数量深搜【深搜2种写法，区别】

题目 ·

思路

总结

99.岛屿数量广搜【广搜的两种写法，bfs,】

题目

思路

总结

100.岛屿的最大面积

题目

思路

总结

最新新闻

热搜词

网页制作实战视频_品牌_北京网聘咨询有限公司_企业员工培训内容及计划

Day57_20250205_图论part3_99.岛屿数量深搜|99.岛屿数量广搜|100.岛屿的最大面积

99.岛屿数量深搜 【深搜2种写法，区别】

题目 ·

思路

总结

99.岛屿数量广搜 【广搜的两种写法，bfs,】

题目

思路

总结

100.岛屿的最大面积

题目

思路

总结

最新新闻

热搜词

99.岛屿数量深搜【深搜2种写法，区别】

99.岛屿数量广搜【广搜的两种写法，bfs,】