刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

香蕉田

编程实现

小猴有一片矩形香蕉林,香蕉林一共被分成了 n x m 个小块,每个小块上会有一颗香蕉树或者是一块空地。我们用 0 表示一块空地,用 1 表示一颗香蕉树,香蕉林之外可以视作全部是空地。

小猴认为一个香蕉田由聚在一起的 1 相连接而组成(上下左右相邻)。

在一个香蕉田 A 中,可以从中选出若干个香蕉树,使得这些香蕉树可以通过上、下、左、右方向连接构成一个“环”。

如果另一个香蕉田 B 所占据的格子全部位于这个“环”内部,就将香蕉田 B 视作香蕉田A 的子香蕉田。

若 B 是 A 的子香蕉田,C 是 B 的子香蕉田,那么 C 也是 A 的子香蕉田。

例如,有 5 x 5 的香蕉林:

其中香蕉田有两个,分别用蓝色区域和绿色区域来表示,但是绿色区域的香蕉田是蓝色区域香蕉田的子香蕉田。如果不统计子香蕉田的个数,那么该香蕉林中只有一个香蕉田。

现在,请你帮助小猴统计一下香蕉林中一共有多少个香蕉田。在进行统计时不需要统计子香蕉田的数目。

输入描述

第一行,包含一个整数 T,表示有 T 组测试数据。( 1≤T≤10 )

对于每一组数据:

第一行包含两个整数 n,m,表示香蕉林的大小。( 1≤n,m≤50 )

接下来的 n 行,每行包含 m 个字符,保证字符只可能是 0 或 1。

输出描述

对于每组数据,输出一行,包含一个整数表示答案。


输入样例

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

输出样例

1
3

样例说明

对于第一组数据,包含两个香蕉田,下面用不同的颜色进行了区分:

绿色香蕉田在蓝色香蕉田的“环”内部,所以绿色香蕉田是蓝色香蕉田的子香蕉田,答案为 1。

对于第二组数据,包含三个香蕉田,下面用不同的颜色进行了区分:

注意橙色香蕉田并不是蓝色香蕉田或者绿色香蕉田的子香蕉田 ,因为蓝色香蕉田和绿色香蕉田中均没有“环”,答案为 3。

使用微信搜索喵呜刷题,轻松应对考试!

答案:

对于每组数据,首先读取n和m,然后读取n行m列的香蕉林。使用深度优先搜索(DFS)遍历香蕉林,每次遍历到一个1时,检查其上下左右四个方向是否也是1,如果是,则将其标记为已访问。如果遍历过程中形成了一个环,并且这个环内所有的格子都被标记为已访问,那么这个环就是一个香蕉田。统计所有的香蕉田的数量即可。

解析:

【喵呜刷题小喵解析】:
这道题目是一个典型的图论问题,需要使用深度优先搜索(DFS)来解决。首先,我们需要读取n和m,然后读取n行m列的香蕉林。对于每个格子,如果它是1,并且它的上下左右四个方向也都是1,那么我们就可以确定这是一个香蕉树。接下来,我们使用DFS来遍历这个香蕉树,每次遍历到一个格子时,我们将其标记为已访问,并且检查它的上下左右四个方向是否也是1,如果是,则继续遍历。如果遍历过程中形成了一个环,并且这个环内所有的格子都被标记为已访问,那么这个环就是一个香蕉田。最后,我们统计所有的香蕉田的数量即可。

由于题目要求统计香蕉田的数量,而不需要统计子香蕉田的数量,因此我们需要在遍历的过程中,对每个环进行独立的统计。如果环内所有的格子都被标记为已访问,那么我们可以将这个环的计数器加一。在遍历完所有的格子之后,输出计数器的值即可。

需要注意的是,如果一个环内有其他环,那么这个环内的子环也会被统计为一个香蕉田。因此,我们需要保证在遍历的过程中,对每个环进行独立的统计,以避免重复统计。
创作类型:
原创

本文链接:香蕉田 编程实现 小猴有一片矩形香蕉林,香蕉林一共被分成了 n x m 个小块,每个小块上会有一颗香

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share