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

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

题目描述

给你一个 n×mn\times m 的地图,地图由 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,地图中的每个元素都是 00 或 11。

只考虑上下左右连通,不能斜着连接。