0200. 岛屿数量 #
- 标签:深度优先搜索、广度优先搜索、并查集、数组、矩阵
- 难度:中等
题目大意 #
描述:给定一个由字符 '1'
(陆地)和字符 '0'
(水)组成的的二维网格 grid
。
要求:计算网格中岛屿的数量。
说明:
- 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
- 此外,你可以假设该网格的四条边均被水包围。
- $m == grid.length$。
- $n == grid[i].length$。
- $1 \le m, n \le 300$。
grid[i][j]
的值为'0'
或'1'
。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
如果把上下左右相邻的字符 '1'
看做是 1
个连通块,这道题的目的就是求解一共有多少个连通块。
使用深度优先搜索或者广度优先搜索都可以。
思路 1:深度优先搜索 #
- 遍历
grid
。 - 对于每一个字符为
'1'
的元素,遍历其上下左右四个方向,并将该字符置为0
,保证下次不会被重复遍历。 - 如果超出边界,则返回
0
。 - 对于
(i, j)
位置的元素来说,递归遍历的位置就是(i - 1, j)
、(i, j - 1)
、(i + 1, j)
、(i, j + 1)
四个方向。每次遍历到底,统计数记录一次。 - 最终统计出深度优先搜索的次数就是我们要求的岛屿数量。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。
- 空间复杂度:$O(m \times n)$。