面试150 岛屿数量

思路

本算法采用深度优先搜索（DFS）策略来统计网格中岛屿的数量。对于网格中的每一个位置，如果其值为 ‘1’ 且尚未被访问，则从该位置开始进行 DFS 遍历。在遍历过程中，程序会递归地向四个方向（上、下、左、右）扩展搜索，凡是遇到值为 ‘1’ 且未访问的格子，均标记为已访问。每启动一次新的 DFS，即发现一个新的岛屿，对应的计数器 count 增加 1。最终返回 count 即为岛屿的总数。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        direction=[(-1,0),(0,-1),(0,1),(1,0)]
        m=len(grid)
        n=len(grid[0])
        visited=[[False]*n for _ in range(m)]
        count=0
        def dfs(i,j,visited):
            for x,y in direction:
                dx=x+i 
                dy=j+y
                if dx<0 or dx>=m or dy<0 or dy>=n:
                    continue
                if grid[dx][dy]=='1' and not visited[dx][dy]:
                    visited[dx][dy]=True
                    dfs(dx,dy,visited)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1' and not visited[i][j]:
                    count+=1
                    visited[i][j]=True 
                    dfs(i,j,visited)
        return count

思路2

具体思路是：遍历整个二维网格，当遇到值为 ‘1’ 且未被访问的位置时，说明发现了一个新的岛屿，此时将该位置加入队列，并启动 BFS。在 BFS 过程中，通过队列依次访问当前位置的四个相邻方向（上、下、左、右），对于值为 ‘1’ 且尚未访问的相邻位置，标记为已访问并加入队列，继续扩展搜索。每次启动新的 BFS 搜索，计数器 count 增加 1，最终返回 count 即为岛屿的总数。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        directions=[[-1,0],[0,-1],[1,0],[0,1]]#确定方向
        def bfs(arr,x,y,visited):
            que=deque([])
            que.append([x,y])
            while que:
                cur_x,cur_y=que.popleft()#队列取出当前坐标
                for i,j in directions:
                    next_x=cur_x+i 
                    next_y=cur_y+j 
                    if next_x<0 or next_x>=len(arr) or next_y<0 or next_y>=len(arr[0]):
                        continue
                    if arr[next_x][next_y]=='1' and not visited[next_x][next_y]:
                        visited[next_x][next_y]=True
                        que.append([next_x,next_y])#加入队列表明该节点走过了
        m=len(grid)
        n=len(grid[0])
        visited=[[False]*n for _ in range(m)]
        count=0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1' and not visited[i][j]:
                    count+=1
                    bfs(grid,i,j,visited)
        return count