A. 【广度优先搜索(二)】岛屿数量

    传统题 1000ms 128MiB

【广度优先搜索(二)】岛屿数量

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一张由 nn 行、mm 列组成的地图,每个格子只有两种状态:

  • 1 表示陆地;
  • 0 表示水域。

如果两个陆地格子在上、下、左、右四个方向上相邻,就认为它们相互连通。若干陆地格子可以通过这样的相邻关系到达彼此,它们共同组成一座岛屿。

注意:斜对角相邻不算连通。地图边界之外视为水域。

请计算这张地图上一共有多少座岛屿。

输入格式

第一行输入两个整数 n,mn,m,表示地图的行数和列数。

接下来 nn 行,每行输入 mm 个整数(0 或 1),相邻整数之间用空格分隔。

输出格式

输出一个整数,表示岛屿的数量。

样例

4 5
0 1 0 1 1
1 1 1 0 0
1 1 0 0 1
0 1 0 1 1
3

样例解释

图中陆地被分成了三个互不连通的部分:左侧一大块、右上角一小块,以及右下角一小块。因此共有 33 座岛屿。

数据范围

1≤n,m≤1001\le n,m\le 100。

地图中的每个数字均为 0 或 1。

周六一点15比赛

未参加
状态
已结束
规则
XCPC
题目
5
开始于
2026-11-14 13:34
结束于
2026-11-14 15:34
持续时间
2 小时
主持人
参赛人数
8