题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

image.png

思路

遍历所有位置，每个位置利用DFS去扫描岛屿边界。

  1. class Solution:
  2.     def numIslands(self, grid: List[List[str]]) -> int:
  3.         if not grid or len(grid) == 0: return 0
  5.         rows, cols = len(grid), len(grid[0])
  6.         count = 0
  7.         for row in range(rows):
  8.             for col in range(cols):
  9.                 if grid[row][col] == '1':
  10.                     count += 1
  11.                     self.dfs(grid, row, col)
  12.         return count
  14.     def dfs(self, grid, row, col):
  15.         if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != '1':
  16.             return
  17.         else:
  18.             grid[row][col] = '2' # 用'2'标记已经访问的位置
  19.             # 探索上下左右四个方向
  21.             self.dfs(grid, row - 1, col) # 上
  22.             self.dfs(grid, row + 1, col) # 下
  23.             self.dfs(grid, row, col - 1) # 左
  24.             self.dfs(grid, row, col + 1) # 右

深度优先搜索

  1. from typing import List
  4. class Solution:
  5.     #        x-1,y
  6.     # x,y-1    x,y      x,y+1
  7.     #        x+1,y
  8.     # 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
  9.     directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
  11.     def numIslands(self, grid: List[List[str]]) -> int:
  12.         m = len(grid)
  13.         # 特判
  14.         if m == 0:
  15.             return 0
  16.         n = len(grid[0])
  17.         marked = [[False for _ in range(n)] for _ in range(m)]
  18.         count = 0
  19.         # 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
  20.         for i in range(m):
  21.             for j in range(n):
  22.                 # 只要是陆地，且没有被访问过的，就可以使用 DFS 发现与之相连的陆地，并进行标记
  23.                 if not marked[i][j] and grid[i][j] == '1':
  24.                     # count 可以理解为连通分量，你可以在深度优先遍历完成以后，再计数，
  25.                     self.__dfs(grid, i, j, m, n, marked)
  26.                     count += 1
  27.         return count
  29.     def __dfs(self, grid, i, j, m, n, marked):
  30.         marked[i][j] = True
  31.         for direction in self.directions:
  32.             new_i = i + direction[0]
  33.             new_j = j + direction[1]
  34.             if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
  35.                 self.__dfs(grid, new_i, new_j, m, n, marked)
  38. if __name__ == '__main__':
  39.     grid = [['1', '1', '1', '1', '0'],
  40.             ['1', '1', '0', '1', '0'],
  41.             ['1', '1', '0', '0', '0'],
  42.             ['0', '0', '0', '0', '0']]
  43.     solution = Solution()
  44.     result = solution.numIslands(grid)
  45.     print(result)

广度优先搜索

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。

  1. from typing import List
  2. from collections import deque
  5. class Solution:
  6.     #        x-1,y
  7.     # x,y-1    x,y      x,y+1
  8.     #        x+1,y
  9.     # 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
  10.     directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
  12.     def numIslands(self, grid: List[List[str]]) -> int:
  13.         m = len(grid)
  14.         # 特判
  15.         if m == 0:
  16.             return 0
  17.         n = len(grid[0])
  18.         marked = [[False for _ in range(n)] for _ in range(m)]
  19.         count = 0
  20.         # 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
  21.         for i in range(m):
  22.             for j in range(n):
  23.                 # 只要是陆地，且没有被访问过的，就可以使用 BFS 发现与之相连的陆地，并进行标记
  24.                 if not marked[i][j] and grid[i][j] == '1':
  25.                     # count 可以理解为连通分量，你可以在广度优先遍历完成以后，再计数，
  26.                     # 即这行代码放在【位置 1】也是可以的
  27.                     count += 1
  28.                     queue = deque()
  29.                     queue.append((i, j))
  30.                     # 注意：这里要标记上已经访问过
  31.                     marked[i][j] = True
  32.                     while queue:
  33.                         cur_x, cur_y = queue.popleft()
  34.                         # 得到 4 个方向的坐标
  35.                         for direction in self.directions:
  36.                             new_i = cur_x + direction[0]
  37.                             new_j = cur_y + direction[1]
  38.                             # 如果不越界、没有被访问过、并且还要是陆地，我就继续放入队列，放入队列的同时，要记得标记已经访问过
  39.                             if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
  40.                                 queue.append((new_i, new_j))
  41.                                 #【特别注意】在放入队列以后，要马上标记成已经访问过，语义也是十分清楚的：反正只要进入了队列，你迟早都会遍历到它
  42.                                 # 而不是在出队列的时候再标记
  43.                                 #【特别注意】如果是出队列的时候再标记，会造成很多重复的结点进入队列，造成重复的操作，这句话如果你没有写对地方，代码会严重超时的
  44.                                 marked[new_i][new_j] = True
  45.                     #【位置 1】
  46.         return count
  49. if __name__ == '__main__':
  50.     grid = [['1', '1', '1', '1', '0'],
  51.             ['1', '1', '0', '1', '0'],
  52.             ['1', '1', '0', '0', '0'],
  53.             ['0', '0', '0', '0', '0']]
  55.     solution = Solution()
  56.     result = solution.numIslands(grid)
  57.     print(result)
  59. 作者：liweiwei1419
  60. 链接：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/
  61. 来源：力扣（LeetCode）
  62. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。