leetcode [200] 岛屿数量

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

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

示例 1:

示例 2:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        memo = [[0] * len(grid[0]) for _ in range(len(grid))]
        num = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and memo[i][j] == 0:
                    self.count(grid, memo, i, j)
                    num += 1
        return num

    def count(self, grid: List[List[str]], memo, i, j) -> int:
        memo[i][j] = 1
        dirs = [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]
        for m, n in dirs:
            if 0 <= m < len(grid) and 0 <= n < len(grid[0]) and memo[m][n] == 0 and grid[m][n] == '1':
                memo[m][n] = 1
                self.count(grid, memo, m, n)