力扣 200. 岛屿数量

dfs

def numIslands(grid):
    def dfs(grid, i, j):
        if not 0 <= i < width or not 0 <= j < height or grid[i][j] == "0": return
        grid[i][j] = "0"
        dfs(grid, i + 1, j)
        dfs(grid,i - 1, j)
        dfs(grid,i, j + 1)
        dfs(grid,i, j - 1)

    width, height = len(grid), len(grid[0])
    ret = 0
    for i in range(width):
        for j in range(height):
            if grid[i][j] == "0":
                continue
            dfs(grid, i, j)
            ret += 1
    return ret

bfs

def numIslands(grid):
    def bfs(grid, i, j):
        queue = [[i, j]]
        while queue:
            for _ in range(len(queue)):
                w, h = queue.pop(0)
                if not 0 <= w < width or not 0 <= h < height or grid[w][h] == "0":
                    continue
                queue.append([w + 1, h])
                queue.append([w - 1, h])
                queue.append([w, h + 1])
                queue.append([w, h - 1])
                grid[w][h] = "0"

    width, height = len(grid), len(grid[0])
    ret = 0
    for i in range(width):
        for j in range(height):
            if grid[i][j] == "0":
                continue
            bfs(grid, i , j)
            ret += 1
    return ret