vegetable

用户名：xx101

访问量：1939

签　名：

等　　级
排　　名	2344
经　　验	2349
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	武软
专　　业

　　自我简介：

TA的其他文章

题目 3155: 蓝桥杯2023年第十四届省赛真题-整数删除
浏览：84

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

排除子岛屿的岛屿计算(bfs+dfs搜索算法遍历)

　　作者: vegetable　　　　发表时间：2023-05-16 22:13:38 浏览：459　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-岛屿个数

###### 题目思考：因为广度优先搜索用得少，第一次碰到此题时只想到用深度优先解决，没想到的是后来我用栈实现dfs(深度)的时候也可以通过。用bfs(广度)要弄清队列和广度优先的特点：后加入队列中的元素要等待栈中元素遍历完：即先进先出，后进后出。类似于求迷宫最短路径等最短路径问题也可用广度优先解决。
------------
###### 代码思路：对总体岛屿用bfs(广度)进行遍历，碰到岛屿时计数变量+1并且用dfs(深度)对连通岛屿染色（改变值）。因为bfs的特点当遍历其它格子时会因岛屿染色过而不会进入到环形岛屿内部。
------------
###### 注意事项：1.bfs(广度)对周围八个格子添加到队列中，等待下一轮遍历。dfs(深度)对周围四个格子进行递归。  2.原二维数组创建时要增加两行两列即最外圈用0包围：一开始我没创建导致代码出现了bug，假设岛屿包围了整个地图答案会出现错误。

```java
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main {
    static int[][] arr1 = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int[][] arr2 = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };
    static int N;
    static int M;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (sc.hasNext()) {
            M = sc.nextInt();
            N = sc.nextInt();
            int[][] arr = new int[M+2][N+2];
            for (int i = 1; i < M+1; i++) {
                String str = sc.next();
                for (int j = 1; j < N+1; j++) {
                    arr[i][j] = Integer.parseInt(str.charAt(j-1) + "");
                }
            }
            System.out.println(sol(arr, M, N));
        }
    }
 `dfs深度优先，利用递归方式实现，对每一个为1的岛屿进行染色，上下左右进入递归`
    public static int sol(int[][] arr, int M, int N) {
        int count = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0 });
        arr[0][0]=2;
        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int X = temp[0];
            int Y = temp[1];
            for (int i = 0; i < 8; i++) {
                int Xi = arr2[i][0]+X;
                int Yi = arr2[i][1]+Y;
                if (Xi >= 0 && Xi < M+2 && Yi >= 0 && Yi < N+2 && arr[Xi][Yi] != 2) {
                    if (arr[Xi][Yi] == 1) {
                        count++;
                        di(Xi, Yi, arr);
                    }else{
                        arr[Xi][Yi] =2;
                        q.add(new int[] { Xi, Yi });
                    }
                }
            }
        }
        return count;
    }
 `dfs深度优先，利用递归方式实现，对每一个为1的岛屿进行染色，上下左右进入递归`
    public static void di(int i, int j, int[][] arr) {
        arr[i][j] = 2;
        for (int i1 = 0; i1 < 4; i1++) {
            int Xi = arr1[i1][0]+i;
            int Yi = arr1[i1][1]+j;
            if (Xi >= 0 && Xi < M+2 && Yi >= 0 && Yi < N+2 && arr[Xi][Yi] == 1) {
                di(Xi,Yi,arr);
            }
        }
    }
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

vegetable

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

排除子岛屿的岛屿计算(bfs+dfs搜索算法遍历)

评论区

精彩推荐

蛇行矩阵（C语言代码）

数字整除（C语言代码）

采药（C++代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

回文串（C语言代码）

vegetable

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

排除子岛屿的岛屿计算(bfs+dfs搜索算法遍历)

评论区

精彩推荐

蛇行矩阵 （C语言代码）

数字整除 （C语言代码）

采药 （C++代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （Java代码）

回文串 （C语言代码）

　　评论区

蛇行矩阵（C语言代码）

数字整除（C语言代码）

采药（C++代码）

C二级辅导-分段函数（C语言代码）

母牛的故事（C语言代码）

回文串（C语言代码）