LeetCode 200. 岛屿数量

当要求出岛屿的数量时，我们可以扫描题目给出的二维网格。如果遍历的元素为 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