银川做网站的公司,做网站应该学什么专业,微信官网手机版,书店如何做网站提示#xff1a; 橙色字体为需要注意部分#xff0c;红色字体为难点部分#xff0c;会在文章“重难点解答”部分精讲。
题目链接
蓝桥杯2023年第十四届省赛真题-岛屿个数 - C语言网
题目理解 这道题让我们求岛屿个数#xff0c;那么我们就应该先弄懂#xff0c;对于一… 提示 橙色字体为需要注意部分红色字体为难点部分会在文章“重难点解答”部分精讲。
题目链接
蓝桥杯2023年第十四届省赛真题-岛屿个数 - C语言网
题目理解 这道题让我们求岛屿个数那么我们就应该先弄懂对于一个岛的定义是什么。我当时就因为没弄明白这个困扰很久所以会将细一点 让我们直观感受下 上图所示情形是一个岛因为外面有了一圈陆地将里面的小陆地包围了起来你可以想象成海岛中的池子中有一块大石头右边的图是我p的是丑了点主要为了便于理解。 而如果是以下情形就变成了两个岛 你可以理解为海水流动性更强而海岛的岩石又不可能衔接的严丝合缝。海水从那个缺口的地方流了进去因此中间小块陆地并没有被外圈陆地包围这种情况下是两个岛。 那么不难理解题目当中给出的第二组示例为什么是3个岛了吧 话不多说我们继续向下进行。
解题思路
1.核心思想 我们用题目给出的第二组用例来讲如下呢就是地图。 然后我们以00为起点使用dfs将外海全部标记为2为了确保00是外海且外海是相通的方便dfs展开我们将地图外部扩展一圈0。 dfs展开将外海全部标记为2 完成 然后对全图进行查找如果有满足标记为‘1’的陆地且与外海相邻对其进行dfs展开标记为3。每进行一次dfs岛屿个数就加1。 2.具体做法
这段代码的思路是通过深度优先搜索DFS来解决问题。下面是代码的详细解释 首先定义了一个二维数组map来表示地图其中map表示格子的状态。0表示海洋1表示未标记的陆地2表示已标记的海洋3表示已标记的陆地。 接下来定义了两个递归函数dfs_sea和dfs_island用于进行深度优先搜索。 dfs_sea函数用于将外海的格子标记为2。从给定的坐标(0, 0)开始如果当前格子是未访问的海洋即map[x][y] 0则将其标记为2并递归调用dfs_sea函数对周围的8个格子进行展开。 dfs_island函数用于将与外海相连的未标记的陆地格子标记为3。从给定的坐标(j, k)开始如果当前格子是未标记的陆地且该格子的上一个上下左右都可以我这里用的是上格子为外海即(1map[j][k])(2map[j-1][k])则将其标记为3并递归调用dfs_island函数对周围的4个格子进行展开。 接下来将二维数组map全部初始化为0。 调用dfs_sea函数从坐标(0, 0)开始将外海的格子标记为2。 接下来使用嵌套循环遍历地图的每个格子如果某个格子是未标记的陆地且与外海相连即当前格子为1上方格子为2则调用dfs_island函数对该陆地进行标记并将计数器count加1。 最后输出计数器count的值表示与外海相连的未标记陆地的数量。
完整代码
#includestdio.h
int m,n,map[52][52];
void dfs_sea(int x,int y)
{if((x0xm1)(y0yn1)){if(0map[x][y])//海水是周围8块进行展开{map[x][y]2;dfs_sea(x,y1);dfs_sea(x,y-1);dfs_sea(x1,y);dfs_sea(x1,y1);dfs_sea(x1,y-1);dfs_sea(x-1,y);dfs_sea(x-1,y1);dfs_sea(x-1,y-1);}}
}
void dfs_island(int x,int y)
{if((x0xm1)(y0yn1)){if(1map[x][y])//陆地是周围4块进行展开{map[x][y]3;dfs_island(x1,y); dfs_island(x-1,y); dfs_island(x,y1);dfs_island(x,y-1);}}
}
main()
{int number;scanf(%d,number);for(int i0;inumber;i){int count0;scanf(%d%d,m,n);for(int j0;jm1;j)//将数组全部初始化为0{for(int k0;kn1;k){map[j][k]0;}}for(int j1;jm;j)//输入地图{for(int k1;kn;k){scanf(%1d,map[j][k]);/*‘%1d’的含义为输入长度为1的整形如果不限制长度则‘11101’会被当场一个数据而不是5个数据*/}}dfs_sea(0,0); //从00处进行dfs将外海全部标记为数字2for(int j1;jm;j){ for(int k1;kn;k){if((1map[j][k])(2map[j-1][k]))
/*当某坐标是未标记过的陆地且其与外海相连对其dfs*/{dfs_island(j,k);count;}}}printf(%d\n,count);}
}
重难点解答
为什么海水8方展开陆地4方展开 如果在这里有问题应该回去再看一下题目理解部分。因为海水可以从陆地的缝隙流过去也就是说海水可以斜着进行扩散而陆地却只能上下左右展开。
———如有问题欢迎评论区提问———
