[Python知识库]python岛屿数量

DFS的递归实现和迭代实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        if grid==None or not len(grid):
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=="1":
                   count += 1
                   #self.dfs(grid,i,j) #递归实现
                   self.dfs_2(grid,i,j) #迭代实现
        
        return count
    
    def dfs(self,grid,i,j):

        if(i<0 or i >= len(grid) or j<0 or j>= len(grid[0]) or grid[i][j]=="0"):
            return
        grid[i][j] = "0"
        self.dfs(grid,i-1,j)
        self.dfs(grid,i+1,j)
        self.dfs(grid,i,j-1)
        self.dfs(grid,i,j+1)

    def dfs_2(self,grid,i,j):
        grid[i][j] = '0'
        stack = [(i,j)]
        
        while(len(stack)):
            (a,b)= (i,j) = stack.pop()
            if (i>0 and grid[i-1][j] !='0'):
                a = i-1
            elif (i<len(grid)-1 and grid[i+1][j] !='0'):
                a = i+1
            elif (j>0 and grid[i][j-1] !='0'):
                b = j-1
            elif (j<len(grid[0])-1 and grid[i][j+1] !='0'):
                b = j + 1
            if (a,b) == (i,j):
                continue
            grid[a][b] = '0'
            stack.append((i,j))
            stack.append((a,b))

BFS的迭代实现

    def bfs(self,grid,i,j):
        grid[i][j] = '0'
        queue = [(i,j)]
        while(len(queue)):
            print(queue)
            (i,j) = queue.pop(0)
            if (i>0 and grid[i-1][j] !='0'):
                grid[i-1][j] = '0'
                queue.append((i-1,j))
            if (i<len(grid)-1 and grid[i+1][j] !='0'):
                grid[i+1][j] = '0'
                queue.append((i+1,j))
            if (j>0 and grid[i][j-1] !='0'):
                grid[i][j-1] = '0'
                queue.append((i,j-1))
            if (j<len(grid[0])-1 and grid[i][j+1] !='0'):
                grid[i][j+1] = '0'
                queue.append((i,j+1))