[蓝桥杯] 岛屿个数（C语言）

    提示： 橙色字体为需要注意部分，红色字体为难点部分，会在文章“重难点解答”部分精讲。

题目链接

蓝桥杯2023年第十四届省赛真题-岛屿个数 - C语言网

题目理解 

        这道题让我们求岛屿个数，那么我们就应该先弄懂，对于一个岛的定义是什么。（我当时就因为没弄明白这个困扰很久，所以会将细一点）

        让我们直观感受下：

        上图所示情形是一个岛，因为外面有了一圈陆地将里面的小陆地包围了起来，你可以想象成海岛中的池子中有一块大石头（右边的图是我p的，是丑了点，主要为了便于理解）。

        而如果是以下情形，就变成了两个岛：

        你可以理解为海水流动性更强，而海岛的岩石又不可能衔接的严丝合缝。海水从那个缺口的地方流了进去，因此中间小块陆地并没有被外圈陆地包围，这种情况下是两个岛。

        那么不难理解题目当中给出的第二组示例为什么是3个岛了吧？

        话不多说，我们继续向下进行。

解题思路 

1.核心思想

        我们用题目给出的第二组用例来讲，如下呢就是地图。

        然后我们以（0，0）为起点使用dfs将外海全部标记为2，为了确保（0，0）是外海且外海是相通的（方便dfs展开），我们将地图外部扩展一圈0。

        dfs展开，将外海全部标记为2

         完成

       然后对全图进行查找，如果有满足标记为‘1’的陆地且与外海相邻，对其进行dfs展开，标记为3。每进行一次dfs，岛屿个数就加1。

2.具体做法 

这段代码的思路是通过深度优先搜索（DFS）来解决问题。下面是代码的详细解释：

1. 首先，定义了一个二维数组map来表示地图，其中map表示格子的状态。0表示海洋，1表示未标记的陆地，2表示已标记的海洋，3表示已标记的陆地。

2. 接下来，定义了两个递归函数dfs_sea和dfs_island，用于进行深度优先搜索。

3. dfs_sea函数用于将外海的格子标记为2。从给定的坐标(0, 0)开始，如果当前格子是未访问的海洋（即map[x][y] == 0），则将其标记为2，并递归调用dfs_sea函数对周围的8个格子进行展开。

4. dfs_island函数用于将与外海相连的未标记的陆地格子标记为3。从给定的坐标(j, k)开始，如果当前格子是未标记的陆地且该格子的上一个（上下左右都可以，我这里用的是上）格子为外海（即(1==map[j][k])&&(2==map[j-1][k])），则将其标记为3，并递归调用dfs_island函数对周围的4个格子进行展开。

5. 接下来，将二维数组map全部初始化为0。

6. 调用dfs_sea函数，从坐标(0, 0)开始，将外海的格子标记为2。

7. 接下来，使用嵌套循环遍历地图的每个格子，如果某个格子是未标记的陆地且与外海相连（即当前格子为1，上方格子为2），则调用dfs_island函数对该陆地进行标记，并将计数器count加1。

8. 最后，输出计数器count的值，表示与外海相连的未标记陆地的数量。

完整代码 

#include<stdio.h>
int m,n,map[52][52];
void dfs_sea(int x,int y)
{if((x>=0&&x<=m+1)&&(y>=0&&y<=n+1)){if(0==map[x][y])//海水是周围8块进行展开{map[x][y]=2;dfs_sea(x,y+1);dfs_sea(x,y-1);dfs_sea(x+1,y);dfs_sea(x+1,y+1);dfs_sea(x+1,y-1);dfs_sea(x-1,y);dfs_sea(x-1,y+1);dfs_sea(x-1,y-1);}}
}
void dfs_island(int x,int y)
{if((x>=0&&x<=m+1)&&(y>=0&&y<=n+1)){if(1==map[x][y])//陆地是周围4块进行展开{map[x][y]=3;dfs_island(x+1,y); dfs_island(x-1,y); dfs_island(x,y+1);dfs_island(x,y-1);}}
}
main()
{int number;scanf("%d",&number);for(int i=0;i<number;i++){int count=0;scanf("%d%d",&m,&n);for(int j=0;j<=m+1;j++)//将数组全部初始化为0{for(int k=0;k<=n+1;k++){map[j][k]=0;}}for(int j=1;j<=m;j++)//输入地图{for(int k=1;k<=n;k++){scanf("%1d",&map[j][k]);/*‘%1d’的含义为输入长度为1的整形，如果不限制长度则‘11101’会被当场一个数据，而不是5个数据*/}}dfs_sea(0,0); //从（0，0）处进行dfs，将外海全部标记为数字2for(int j=1;j<=m;j++){ for(int k=1;k<=n;k++){if((1==map[j][k])&&(2==map[j-1][k]))
/*当某坐标是未标记过的陆地且其与外海相连，对其dfs*/{dfs_island(j,k);count++;}}}printf("%d\n",count);}
}

重难点解答

为什么海水8方展开，陆地4方展开

        如果在这里有问题，应该回去再看一下题目理解部分。因为海水可以从陆地的缝隙流过去，也就是说海水可以斜着进行扩散，而陆地却只能上下左右展开。

———（如有问题，欢迎评论区提问）———