岛屿数量问题。BFS解决方案很慢，试图找出瓶颈

Question

给定“1”（陆地）和“0”（水）的m x n二维栅格地图，返回岛屿数

岛屿被水包围，通过水平或垂直连接相邻的陆地而形成。您可以假设网格的所有四条边都被水包围

https://leetcode.com/problems/number-of-islands/

我的解决方案：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        no = 0 # number of islands
        visited = set()
        rows, cols = len(grid), len(grid[0])

        def visit(row, col):
            if (row, col) in visited or grid[row][col] != "1": return False

            q = deque()
            q.append((row, col))

            while q:
                row, col = q.popleft()
                if (row, col) in visited or grid[row][col] != "1": continue

                visited.add((row, col))

                # Visit left
                if col > 0:
                    q.append((row, col - 1))

                # Visit right
                if col < cols - 1: 
                    q.append((row, col + 1))

                # Visit top
                if row > 0:
                    q.append((row - 1, col))

                # Visit bottom
                if row < rows - 1: 
                    q.append((row + 1, col))

            return True

        for row in range(rows):
            for col in range(cols):
                if visit(row, col):
                    no += 1
        return no

它只比约40%的解决方案好，因此显然有些地方可以改进。这是怎么一回事？我错过了什么

Answer 1

您不需要使用不同的编号对不同的岛屿进行分类。因为您只关心grid[row][col]是否为“1”，所以在您访问每个岛屿后，只需将它们设置为“0”，这样您就不会再次访问它们

从输入导入列表开始 从集合导入deque

类解决方案： def初始化（自身）： 自身方向=[[1,0]，-1,0]，[0,1]，[0,1]，[0,1]]

def numIslands(self,grid:List[List[int]])->int:
        ROWS,COLS=len(grid),len(grid[0])
        count=0

        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col]=="1":
                    count+=1
                    stack=deque()
                    stack.append([row,col])
                   # I found the first "1", I added to queue, and then make its value "0"
                    grid[row][col]="0"
                   # stack keeps all "1"s in the same island
                    while len(stack):
                        current=stack.popleft()
                        current_row=current[0]
                        current_col=current[1]
                        for direction in self._directions:
                            new_row=current_row+direction[0]
                            new_col=current_col+direction[1]
                            if new_row<0 or new_row>=ROWS or new_col<0 or new_col>=COLS:
                                continue
                            if grid[new_row][new_col]=="1":
                                stack.append([new_row,new_col])
                                # I found another "1" in the same island, push it to stack and make its value "0"
                                grid[new_row][new_col]="0"
        return count

Answer 2

我很确定这是因为你正在维护的访问集。这可以很容易地删除，因为您可以在位编辑矩阵以跟踪访问的节点

1. 删除该集将缩短时间，因为不再对该集执行插入/删除/查找操作
2. 您只需对节点编号即可。与使用-1标记第一个孤岛中的所有节点一样，使用-2标记第二个孤岛中的节点，以此类推，将删除该集并使其更易于求解