岛屿数量
Number of Islands
本机进度仅保存在当前浏览器
题目描述
给你一个由 1（陆地）和 0（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
示例：网格 [["1","1","0"],["1","0","0"],["0","0","1"]] 有 2 个岛屿。
解题思路
- 岛屿 = 陆地格子的连通分量。遍历所有格子，遇到未访问的陆地时计数加一，并把整片相连的陆地"淹掉"。
- DFS 从当前位置向四方向递归扩散；BFS 用队列逐层扩散，效果等价。
- 标记访问可直接把格子改写为 0（或 2），省去 visited 矩阵，且不影响后续判断。
参考实现
查看参考实现Python · 建议先自行作答
def numIslands(grid):
m, n = len(grid), len(grid[0])
def sink(i, j):
# 深度优先把整片陆地标记为水
if not (0 <= i < m and 0 <= j < n) or grid[i][j] != '1':
return
grid[i][j] = '0'
sink(i + 1, j)
sink(i - 1, j)
sink(i, j + 1)
sink(i, j - 1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
sink(i, j)
return count