BFS 相同的方式不同的结果 (python)

Question

问题：https://leetcode.com/problems/number-of-islands/

试图弄清楚为什么根据测试用例调用 bfs 函数会导致“正确”的行为，而只编写没有函数调用的纯代码则不会。这实际上是相同的代码。

class Solution:

    def bfs(self, grid, queue):
       
        while len(queue) != 0:
            
            i, j = queue.pop(0)

            if i - 1 >= 0 and grid[i - 1][j] == "1":
                grid[i - 1][j] = "0"
                queue.append((i - 1, j))

            if i + 1 < len(grid) and grid[i + 1][j] == "1":
                grid[i + 1][j] = "0"
                queue.append((i + 1, j))

            if j - 1 >= 0 and grid[i][j - 1] == "1":
                grid[i][j - 1] = "0"
                queue.append((i, j - 1))

            if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
                grid[i][j + 1] = "0"
                queue.append((i, j + 1))

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

        sol = 0

        for i in range(0, len(grid), 1):
            for j in range(0, len(grid[i]), 1):

                if grid[i][j] == "1":
                    sol += 1
            
                    queue = [(i, j)]

                    grid[i][j] = "0"
                    
# calling the function does different behavior
#                     self.bfs(grid, queue)
    
# as opposed to not calling the bfs function:           
#                     while len(queue) != 0:
#                         print(queue)
#                         i, j = queue.pop(0)

#                         if i - 1 >= 0 and grid[i - 1][j] == "1":
#                             grid[i - 1][j] = "0"
#                             queue.append((i - 1, j))

#                         if i + 1 < len(grid) and grid[i + 1][j] == "1":
#                             grid[i + 1][j] = "0"
#                             queue.append((i + 1, j))

#                         if j - 1 >= 0 and grid[i][j - 1] == "1":
#                             grid[i][j - 1] = "0"
#                             queue.append((i, j - 1))

#                         if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
#                             grid[i][j + 1] = "0"
#                             queue.append((i, j + 1))

        return sol

测试用例：

[["1","0","0","1","1","1","0","1","1","0","0","0","0","0","0","0","0","0","0","0"],["1","0","0","1","1","0","0","1","0","0","0","1","0","1","0","1","0","0","1","0"],["0","0","0","1","1","1","1","0","1","0","1","1","0","0","0","0","1","0","1","0"],["0","0","0","1","1","0","0","1","0","0","0","1","1","1","0","0","1","0","0","1"],["0","0","0","0","0","0","0","1","1","1","0","0","0","0","0","0","0","0","0","0"],["1","0","0","0","0","1","0","1","0","1","1","0","0","0","0","0","0","1","0","1"],["0","0","0","1","0","0","0","1","0","1","0","1","0","1","0","1","0","1","0","1"],["0","0","0","1","0","1","0","0","1","1","0","1","0","1","1","0","1","1","1","0"],["0","0","0","0","1","0","0","1","1","0","0","0","0","1","0","0","0","1","0","1"],["0","0","1","0","0","1","0","0","0","0","0","1","0","0","1","0","0","0","1","0"],["1","0","0","1","0","0","0","0","0","0","0","1","0","0","1","0","1","0","1","0"],["0","1","0","0","0","1","0","1","0","1","1","0","1","1","1","0","1","1","0","0"],["1","1","0","1","0","0","0","0","1","0","0","0","0","0","0","1","0","0","0","1"],["0","1","0","0","1","1","1","0","0","0","1","1","1","1","1","0","1","0","0","0"],["0","0","1","1","1","0","0","0","1","1","0","0","0","1","0","1","0","0","0","0"],["1","0","0","1","0","1","0","0","0","0","1","0","0","0","1","0","1","0","1","1"],["1","0","1","0","0","0","0","0","0","1","0","0","0","1","0","1","0","0","0","0"],["0","1","1","0","0","0","1","1","1","0","1","0","1","0","1","1","1","1","0","0"],["0","1","0","0","0","0","1","1","0","0","1","0","1","0","0","1","0","0","1","1"],["0","0","0","0","0","0","1","1","1","1","0","1","0","0","0","1","1","0","0","0"]]

调用函数returns预期的解决方案：58 不打电话时 returns: 47

Answer 1

您的解决方案的大图：

        for i in range(0, len(grid), 1):
            for j in range(0, len(grid[i]), 1):
                run BFS

如果您就在那里编写 BFS 代码，它会弄乱外循环中的变量 i（还有 j，但这并不重要）。如果您改为调用函数，该函数有自己的局部变量 i 并且不会弄乱循环。

BFS 相同的方式不同的结果 (python)

BFS same way different result (python)

python

breadth-first-search