岛屿数量 -- 二维矩阵的dfs算法

岛屿数量

又被称为 FloodFill 算法

class NumIslands:
    """
    floodFill 算法
    https://leetcode.cn/problems/number-of-islands/
    """
    def solution(self, grid: List[List[str]]) -> int:
        res = 0
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    self.dfs_matrix(grid, i, j)

        return res

    def dfs_matrix(self, grid, i, j):
        m, n = len(grid), len(grid[0])

        # 跳出递归条件
        if i < 0 or i >= m or j < 0 or j >= n:
            return

        if grid[i][j] == '0':
            return
        grid[i][j] = '0'
        self.dfs_matrix(grid, i - 1, j)  # 上
        self.dfs_matrix(grid, i + 1, j)  # 下
        self.dfs_matrix(grid, i, j - 1)  # 左
        self.dfs_matrix(grid, i, j + 1)  # 右
        

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33