题解 | #岛屿数量#

本题使用了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