23年8月-B组(才俊)
Contest is over.
开始 2023-08-12 00:00:00
当前 2024-07-03 05:48:05
结束 2023-08-13 23:00:00

D. 子岛屿统计

题目描述

生态学家 A 教授,正在研究某个海域中的生态系统。他知道在这个海域中有很多小岛,研究需要了解这些小岛之间的关系,以便更好地理解这个海域中的生态系统。

为了完成这项研究,作为小助手的你需要编写一段程序来计算两个岛屿之间的关系。

具体来说,你需要根据给定两个大小为 m \times n 的岛屿地图 G1G2,输出 G2 中子岛屿的数量。

G1G2 中的岛屿定义为:在地图中 1 表示陆地,0 表示海洋。某个陆地四方向连通的所有的陆地构成一个岛屿。

例如,下方左图中有 1 个岛屿,下方右图中有 2 个岛屿。

G2 的子岛屿指的是,从地图上来看, G2 的某个岛屿包含的每块陆地,在 G1 中的同一个位置上,也是陆地。

例如,G1 如果是下方左图,G2 如果是下方右图。则 G2 中有 3 个岛屿:一个绿色和两个红色。绿色的岛屿无法满足其包含的每块陆地在 G1 的同一个位置上也是陆地。但红色的岛屿满足其包含的每块陆地在 G1 的同一个位置上也是陆地,因此 G2 中有 2 个子岛屿。

输入

第一行输入边长 mn

加下来输入 2m \times n 的矩阵,分别表示 G1G2 两个地图的信息,其中 1 表示岛屿的陆地部分,0 表示海洋,数据保证矩阵中每个值不是 1 就是 0

输出

子岛屿的数量。

样例

输入

2 8
0 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 

输出

0

输入

5 5
1 0 1 0 0
0 1 1 1 1
0 0 0 0 0
1 0 1 0 0
1 1 0 1 1
0 0 0 0 0
1 1 1 1 1
0 1 0 1 0
0 1 0 1 0
1 0 0 0 1

输出

2

输入

1 2
1 1
0 1

输出

1
说明

【样例 1 解释】

如下图所示,左边为 G1 ,右边为 G2

G2 中共有 2 个岛屿,但这两个岛屿都不是子岛屿。

【样例 2 解释】

如下图所示,左边为 G1 ,右边为 G2G2 中标红的的岛屿是子岛屿,总共有 2 个子岛屿。

【样例 3 解释】

如下图所示,左边为 G1 ,右边为 G2G2 中标红的区域是子岛屿,总共有 1 个子岛屿。

【数据范围】

对于 100\% 的数据满足:1 \le m, n \le 500

编辑代码
登录

注册
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 216
通过人数 114
金币数量 0 枚
难度 基础
提交