1020. 飞地的数量 #
- 标签:深度优先搜索、广度优先搜索、并查集、数组、矩阵
- 难度:中等
题目大意 #
描述:给定一个二维数组 grid
,每个单元格为 0
(代表海)或 1
(代表陆地)。我们可以从一个陆地走到另一个陆地上(朝四个方向之一),然后从边界上的陆地离开网络的边界。
要求:返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
说明:
- $m == grid.length$。
- $n == grid[i].length$。
- $1 \le m, n \le 500$。
- $grid[i][j]$ 的值为 $0$ 或 $1$。
示例:
|
|
|
|
解题思路 #
思路 1:深度优先搜索 #
与四条边界相连的陆地单元是肯定能离开网络边界的。
我们可以先通过深度优先搜索将与四条边界相关的陆地全部变为海(赋值为 0
)。
然后统计网格中 1
的数量,即为答案。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。
- 空间复杂度:$O(m \times n)$。