题目

给你一个由 ‘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'
  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. class Solution:
  2.     def numIslands(self, grid: List[List[str]]) -> int:
  3.         rows, cols = len(grid), len(grid[0])
  4.         if rows == 0 or cols == 0: return 0
  5.         visited = grid[:][:] # 用于标记访问过的位置
  6.         count = 0 # 岛屿数量
  7.         for row in range(rows):
  8.             for col in range(cols):
  9.                 if grid[row][col] == '1' and visited[row][col] != -1:
  10.                     self.dfs(row, col, visited, rows, cols, grid)
  11.                     count += 1
  12.         print(visited)
  13.         return count
  15.     def dfs(self, row, col, visited, rows, cols, grid):
  16.         if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0' or visited[row][col] == -1:
  17.             return
  18.         visited[row][col] = -1
  19.         # 上下左右
  20.         self.dfs(row - 1, col, visited, rows, cols, grid)
  21.         self.dfs(row + 1, col, visited, rows, cols, grid)
  22.         self.dfs(row, col - 1, visited, rows, cols, grid)
  23.         self.dfs(row, col + 1, visited, rows, cols, grid)