本题使用了dfs来进行岛屿数的计算。

首先介绍dfs,当地图上的一个格子是陆地的时候,那么我们会很自然地想知道他周围的格子是否也是陆地。所以当发现矩阵中某个元素为‘1’时(其index 为 r, c),我们首先将其置为 0, 意思为我们已经踏足了该陆地格子,之后从它出发的 四个方向[(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] 各走一个格子我们来判断是否为陆地,当然还要注意四个格子不能越界, 只要是的话我们就将其变成 0, 然后继续从这个格子出发,往它的四个周围格子检查,依次递归往复,这样我们就踏足了某个岛屿上面的所有陆地格子,并且消去了整个小岛。

在遍历整个地图(矩阵)的过程中,我们可以通过上述方法,来完成对岛屿数量计数的任务。

class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        def dfs(grid, r, c):
            grid[r][c] = 0
            nr = len(grid) - 1
            nc = len(grid[0]) - 1
            for i, j in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
                    if 0 <= i <= nr and 0 <= j <= nc and grid[i][j] == '1':
                        dfs(grid, i, j)
        if len(grid) == 0:
            return 0
        row = len(grid)
        col = len(grid[0])
        num_island = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    num_island += 1
                    dfs(grid, i, j)
        return num_island