#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        if not grid:
            return None
        m = len(grid)
        n = len(grid[0])

        def dfs(grid, i, j):
            grid[i][j] = '0'

            if i - 1 >= 0 and grid[i-1][j] == '1':
                dfs(grid, i-1, j)
            if i + 1 < m and grid[i+1][j] == '1':
                dfs(grid, i+1, j)
            if j - 1 >= 0 and grid[i][j-1] == '1':
                dfs(grid, i, j-1)
            if j + 1 < n and grid[i][j+1] == '1':
                dfs(grid, i, j+1)

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(grid, i, j)
        return count

解题思路

• 先处理矩阵为空的情况；
• 然后遍历矩阵，当元素值为1的时候，将计数器加一，并将其周围的元素都置为0（跳转到dfs函数）。
• dfs函数实现了将grid[i][j]连通的为1的元素都置为0。

复杂度

• 时间复杂度为O（mn）;
• 空间复杂度为O（mn），栈递归的空间复杂度。