1327 - 岛屿数量

通过次数

52

提交次数

121

时间限制 : 1 秒
内存限制 : 512 MB

岛屿总是被水包围,并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。现在输入整数m、n(1≤m,n≤300),再输入一个大小为 m × n由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量并输出岛屿的数量。

输入

第一行输入两个正整数m和n,表示大小为m × n的矩阵
接下来的m行,每行输入由0或1组成的n个数,表示矩阵中的陆地和水。

输出

一行一个整数,表示网格中岛屿的数量

样例

输入

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

输出

3

提示

样例输出的3座岛屿数量如下图所示,染色部分为岛屿。

岛屿问题可以理解为一类网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0(蓝色块) 的格子看成海洋格子,数字为 1(棕色块) 的格子看成陆地格子,这样相邻的陆地格子就连接成一个岛屿,而题目的要求就是找出岛屿的数量。同样岛屿问题可以演化各种岛屿问题的变种,包括岛屿的数量、面积(‘1’块的个数)、周长(‘1’块的边界长度等)等。不过这些问题,基本都可以用 DFS 遍历来解决。