题目

给定一个由 1（陆地）和 0（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。假设网格的四个边均被水包围。

示例 1:

示例 2:

方案一（BFS）

def numIslands(grid: [[str]]) -> int:
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0  # 岛屿数量
    used = set()
    deque = collections.deque()

    for i in range(m):
        for j in range(n):
            if grid[i][j] == "0": # 跳过水
                continue
            if (i, j) in used:  # 已经遍历过
                continue

            used.add((i, j))
            deque.append((i, j))
            # bfs
            while len(deque) > 0:
                coor = deque.popleft()
                for x, y in [(coor[0] + 1, coor[1]), (coor[0] - 1, coor[1]), (coor[0], coor[1] + 1), (coor[0], coor[1] - 1)]:
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == "1" and (x, y) not in used:
                        used.add((x, y))
                        deque.append((x, y))
            count += 1

    return count

直接使用bfs

方案二（DFS）

def numIslands(grid: [[str]]) -> int:
  if not grid or not grid[0]:
      return 0

  m = len(grid)
  n = len(grid[0])

  def DFS(curr, visited):
      '''运行一次DFS，运行时将访问过的节点全都放在visited中，目标节点为0'''
      if grid[curr[0]][curr[1]] == "0" or not curr:
          return
      for x, y in [(curr[0] + 1, curr[1]), (curr[0] - 1, curr[1]), (curr[0], curr[1] + 1), (curr[0], curr[1] - 1)]:
          if 0 <= x < m and 0 <= y < n and (x, y) not in visited:
              visited.add((x, y))
              DFS((x, y), visited)
      return

  visited = set()
  count = 0
  for i in range(m):
      for j in range(n):
          if (i, j) in visited or grid[i][j] == "0": # 跳过访问过的和水
              continue
          DFS((i, j), visited)
          count += 1

  return count

原文

https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/872/