讨论/《队列 & 栈》 - 岛屿数量/
《队列 & 栈》 - 岛屿数量

参照大@sdwwld写的Python版本的dfs和bfs:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        from queue import Queue
        if not grid or len(grid) == 0:
            return 0
        res = 0

        def dfs(grid, i, j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return False
            grid[i][j] = '0'
            dfs(grid, i-1, j)
            dfs(grid, i+1, j)
            dfs(grid, i, j-1)
            dfs(grid, i, j+1)

        def bfs(grid, x, y):
            grid[x][y] = '0'
            n, m = len(grid), len(grid[0])
            queue = Queue()
            code = x*m + y
            queue.put(code)
            while not queue.empty():
                code = queue.get()
                i, j = code//m, code%m
                if i > 0 and grid[i-1][j] == '1':
                    grid[i-1][j] = '0'
                    queue.put((i-1)*m+j)
                if i < n-1 and grid[i+1][j] == '1':
                    grid[i+1][j] = '0'
                    queue.put((i+1)*m+j)
                if j > 0 and grid[i][j-1] == '1':
                    grid[i][j-1] = '0'
                    queue.put(i*m+j-1)
                if j < m-1 and grid[i][j+1] == '1':
                    grid[i][j+1] = '0'
                    queue.put(i*m+j+1)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    res += 1
                    dfs(grid, i, j)
        return res
展开全部 16 讨论