当前位置：网站首页>Leetcode200-查找岛屿数量详解

使用DFS方法的思想进行分析，首先第一步可以设置一个指针，指针初始指向（0,0）的位置，由于只能上下左右的1能构成岛屿，所以第二步将（0,0）位置上下左右的1变成0，证明这些1已经与（0,0）位置构成了岛屿，然后第三步再将指针指向（0,1）位置移动，第四步同样将上下左右的1变成0，然后再移动，直到当前位置的上下左右全部为0没有1时，说明当前岛屿已经结束，再继续移动找下一个岛屿，直到到达整个二维数组的最后。

根据示例2详细分析

当指针继续移动到（0,2）的位置时，此位置的上下左右全部为0，说明没有符合的1能继续组成岛屿，所以此时岛屿1已经全部找到。

继续移动指针，去找下一个岛屿......

当指针移动到（2，2）的位置时，出现了1，说明又有新的岛屿出现了，同样进行1变0的操作，但是此时上下左右都是0，说明岛屿已经全部找到，这是一个“小岛屿”

同样继续移动指针，去找下一个岛屿......

当指针移动到（3,3）的位置时又出现了1，说明有新的岛屿出现，将上下左右的1变为0

当指针移动到最后时，所有区域都已经遍历完了

BFS

BFS方法的过程也是找上下左右的1的过程，不过这里要用到队列，大致过程为第一步将指针指向（0,0）的位置，第二步将该位置的坐标放入队列中，第三步从队列中取出坐标位置，第四步将坐标上下左右为1的位置放入队列中

第五步将上下左右为1的位置变为0，第六步取出队列第一个元素，并将其上下左右为1的位置放入队列，第七步将为1的位置变成0

依次取出队列中的坐标，并判断上下左右是否有1，直到队列中没有坐标

移动指针，直到移动到下一个为1 的位置，则找到第二个岛屿

移动指针，找到第三个岛屿

代码

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:  # 如果整个区域为空，则无岛屿，直接返回0
            return 0
        
        result = 0  # 记录岛屿数量
        row = len(grid)  # 整个区域的行数
        col = len(grid[0])  # 整个区域的列数
        
        # 用2个for循环遍历整个区域
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '1':  # 找到了新岛屿
                    result += 1
                    self.dfs(grid, i, j, row, col) 
        return result

    def dfs(self, grid, x, y, row, col): # (x,y)为当前指针所指位置
        # x,y在区域外时直接停止循环
        if x<0 or y<0 or x>=row or y>= col or grid[x][y]=='0':
            return
        
        grid[x][y] = '0'  #将1变0

        # 找上下左右为1的位置变0
        self.dfs(grid, x-1, y, row, col)  # 左边变0
        self.dfs(grid, x+1, y, row, col)  # 右边变0
        self.dfs(grid, x, y-1, row, col)  # 上边变0
        self.dfs(grid, x, y+1, row, col)  # 下边变0

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:  # 如果整个区域为空，则无岛屿，直接返回0
            return 0
        
        result = 0  # 记录岛屿数量
        row = len(grid)  # 整个区域的行数
        col = len(grid[0])  # 整个区域的列数
        queue = []
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '1':
                    result += 1
                    queue.append([i,j])
                    grid[i][j] = '0'
                    while len(queue) > 0:
                        cur = queue.pop()
                        x = cur[0]
                        y = cur[1]
                        if x-1 >= 0 and grid[x-1][y] == '1':
                            queue.append([x-1,y])
                            grid[x-1][y] = '0'
                        if y-1 >= 0 and grid[x][y-1] == '1':
                            queue.append([x,y-1])
                            grid[x][y-1] = '0'
                        if x+1 < row and grid[x+1][y] == '1':
                            queue.append([x+1,y])
                            grid[x+1][y] = '0'
                        if y+1 < col and grid[x][y+1] == '1':
                            queue.append([x,y+1])
                            grid[x][y+1] = '0'
        return result

原网站

版权声明
本文为[白羊by]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_45848575/article/details/125969230