200. 岛屿数量
题目来源：https://leetcode-cn.com/problems/number-of-islands/
题目
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路
方法一：深度优先搜索
当要求出岛屿的数量时，我们可以扫描题目给出的二维网格。如果遍历的元素为 1，则以这个位置为起点进行深度优先搜索。
这里需要注意的是：深度优先搜索的过程中，已经搜索到的 1 要标记为 0，表示已经访问过。
那么进行深度优先搜索的次数就是要求的岛屿的数量。
详细部分见代码注释。
方法二：广度优先搜索
同样的，这道题也可以使用广度优先搜索进行替换解答。不过，这里需要增加一个辅助队列。
同样的，求岛屿的数量，先扫描遍历二维网格，如果遍历的位置元素为 1，要将其加入队列，同时标记为访问过，这里同样避免重复被加入队列中，导致代码运行超时。（如果遇到超时的情况，可检查队列中的变化是否有重复添加的现象。）直到队列为空时，搜索结束。
同样进行广度优先搜索的次数就是要求的岛屿数量。
文字表述比较繁琐难懂，可以结合代码了解思想。
具体的代码实现如下。
代码实现
方法一: 深度优先搜索 | 代码实现
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
# 四个方位
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def _dfs(grid, x, y):
# 进行深度优化搜索，标记已访问
grid[x][y] = '0'
for dx, dy in directions:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
_dfs(grid, nx, ny)
ans = 0
for x in range(m):
for y in range(n):
# 遍历，当为陆地时，进行深度优化搜索
if grid[x][y] == '1':
ans += 1
_dfs(grid, x, y)
return ans
方法二: 广度优先搜索 | 代码实现
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
from collections import deque
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
ans = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for row in range(m):
for col in range(n):
# 扫描遍历，
# 当为陆地，进行广度优化搜索
if grid[row][col] == '1':
ans += 1
# 标记已经访问
grid[row][col] = '0'
# 创建辅助队列，同时防止重复搜索
queue = deque([(row, col)])
# 队列不为空的情况下，继续进行搜索
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
# 入队列，防止重复
queue.append((nx, ny))
# 标记已访问
grid[nx][ny] = '0'
return ans
实现结果
方法一: 深度优先搜索 | 实现结果
深度优化搜索 | 实现结果
方法二: 广度优先搜索 | 实现结果
广度优化搜索 | 实现结果
以上就是使用深度优先搜索或广度优先搜索的思想，解决《200. 岛屿数量》问题的主要内容。主要需要注意的地方是：当已经搜索的地方，需要及时标记，避免重复搜索。
欢迎关注微信公众号《书所集录》
