BFS算法的时限

Question

它是leetcode #200，岛屿的数量。我的代码是

def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(i,j):
            q = deque([[i,j]])
            while q:
                r,c = q.popleft()
                if 0<=r<len(grid) and 0<=c<len(grid[0]) and grid[r][c]=="1":
                    grid[r][c]="0"
                    q += [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=="1":
                    count+=1
                    bfs(i,j)

        return count

效果很好。但是当我将bfs函数转换为

def bfs(i,j):
    q = deque([[i,j]])
    while q:
        r,c = q.popleft()
        grid[r][c]="0"
        for d in [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]:
            if 0<=d[0]<len(grid) and 0<=d[1]<len(grid[0]) and grid[d[0]][d[1]]=="1":
                q.append(d)

它给了我超过错误的时限，可能的原因是什么？我觉得这两种密码几乎是一样的？

Answer 1

你多次访问同一个州：

改为：

def bfs(i,j):
    q = deque([[i,j]])
    grid[i][j]="0"

    while q:
        r,c = q.popleft()
        for d in [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]:
            if 0<=d[0]<len(grid) and 0<=d[1]<len(grid[0]) and grid[d[0]][d[1]]=="1":
                grid[d[0]][d[1]]="0"
                q.append(d)