岛屿总是被水包围,并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。现在输入整数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 遍历来解决。