生态学家 A 教授,正在研究某个海域中的生态系统。他知道在这个海域中有很多小岛,研究需要了解这些小岛之间的关系,以便更好地理解这个海域中的生态系统。
为了完成这项研究,作为小助手的你需要编写一段程序来计算两个岛屿之间的关系。
具体来说,你需要根据给定两个大小为 m \times n 的岛屿地图 G1 和 G2,输出 G2 中子岛屿的数量。
G1 和 G2 中的岛屿定义为:在地图中 1 表示陆地,0 表示海洋。某个陆地四方向连通的所有的陆地构成一个岛屿。
例如,下方左图中有 1 个岛屿,下方右图中有 2 个岛屿。
G2 的子岛屿指的是,从地图上来看, G2 的某个岛屿包含的每块陆地,在 G1 中的同一个位置上,也是陆地。
例如,G1 如果是下方左图,G2 如果是下方右图。则 G2 中有 3 个岛屿:一个绿色和两个红色。绿色的岛屿无法满足其包含的每块陆地在 G1 的同一个位置上也是陆地。但红色的岛屿满足其包含的每块陆地在 G1 的同一个位置上也是陆地,因此 G2 中有 2 个子岛屿。
第一行输入边长 m,n。
加下来输入 2 个 m \times n 的矩阵,分别表示 G1、G2 两个地图的信息,其中 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 ,右边为 G2 。 G2 中标红的的岛屿是子岛屿,总共有 2 个子岛屿。
【样例 3 解释】
如下图所示,左边为 G1 ,右边为 G2 。 G2 中标红的区域是子岛屿,总共有 1 个子岛屿。
【数据范围】
对于 100\% 的数据满足:1 \le m, n \le 500。
时间限制 | 1 秒 |
内存限制 | 512 MB |
提交次数 | 216 |
通过人数 | 114 |
金币数量 | 0 枚 |
难度 | 基础 |