题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

输入:
11110
11010
11000
00000
输出: 1
示例 2:

输入:
11000
11000
00100
00011
输出: 3

遍历–>两种思路: DFS 或者 BFS

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if not nr:
            return 0
        nc = len(grid[0])
        counter = 0
        def dfs(r,c):
            grid[r][c] = '0'
            for x, y in [(r,c-1), (r,c+1), (r+1,c), (r-1,c)]:
                if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
                    dfs(x,y)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    counter += 1
                    dfs(r,c)
        return counter

时间复杂度：O(MN)
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MMN。
。

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if not nr:
            return 0
        nc = len(grid[0])
        counter = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    counter += 1
                    grid[r][c] = '0'
                    neighbor = collections.deque([(r, c)])
                    while neighbor:
                        row, col = neighbor.popleft()
                        for x, y in [(row, col-1), (row, col+1), (row+1, col), (row-1, col)]:
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                                neighbor.append((x, y))
                                grid[x][y] = '0'
        return counter

时间复杂度：O(MN)
空间复杂度：O(min(M,N))
在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。
因为BFS是分层遍历的，离出发点最近的一层遍历完再遍历下一层，队列中存放的元素数量最多就是层数的最大值，在这个矩阵中层数是min(M,N),所以空间复杂度是O(min(M,N))

最后

以上就是笑点低信封为你收集整理的200. 岛屿数量 python题目DFSBFS的全部内容，希望文章能够帮你解决200. 岛屿数量 python题目DFSBFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。