在哈希集中使用clear()与copy()

Question

我正在 lintcode 上解决这个问题

我首先想出了以下解决方案，但我失败了一些测试用例

from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        ROWS, COLS = len(rooms), len(rooms[0])
        visited = set()
        def dfs(row, col, distance):
            if row not in range(ROWS) or col not in range(COLS):
                return
            if (row, col) in visited:
                return
            if rooms[row][col] == -1:
                return
            if distance > rooms[row][col]:
                return

            visited.add((row, col))
            rooms[row][col] = min(distance, rooms[row][col])

            dfs(row + 1, col, distance + 1)
            dfs(row - 1, col, distance + 1)
            dfs(row, col + 1, distance + 1)
            dfs(row, col - 1, distance + 1)

        for row in range(ROWS):
            for col in range(COLS):
                if rooms[row][col] == 0:
                    visited.clear()  # Clear the visited set before each traversal
                    dfs(row, col, 0)

然后我环顾四周看看为什么会这样，我看到一个建议，即传递哈希集的不同副本将解决它，所以我执行了以下操作并通过了所有测试用例。

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        ROWS, COLS = len(rooms), len(rooms[0])

        def dfs(row, col, distance, visited):
            if row not in range(ROWS) or col not in range(COLS):
                return
            if (row, col) in visited:
                return
            if rooms[row][col] == -1:
                return
            if distance > rooms[row][col]:
                return

            visited.add((row, col))
            rooms[row][col] = min(distance, rooms[row][col])

            dfs(row + 1, col, distance + 1, visited.copy())
            dfs(row - 1, col, distance + 1, visited.copy())
            dfs(row, col + 1, distance + 1, visited.copy())
            dfs(row, col - 1, distance + 1, visited.copy())

        for row in range(ROWS):
            for col in range(COLS):
                if rooms[row][col] == 0:
                    dfs(row, col, 0, set())

我很困惑为什么传递visited.copy()可以解决问题。我知道当我们传递 Visited.copy() 时，我们传递的是副本而不是哈希集的引用。这是有道理的，但在我的原始代码中，我正在执行visited.clear()，所以这不会达到同样的效果吗？我想如果有人能向我解释这一点，那将非常有帮助，因为我迷路了。

我的意思是，如果 dfs 调用并行发生，但它们没有并行发生，那么我会得到它，所以为什么我需要传递visited.copy()。

Answer 1

如果您不想执行

.copy()

，则需要删除在每个 

(row, col)

 调用之间添加的 

dfs()

。

由于您执行了

dfs

 而不是 

bfs

，因此您无法跳过 

rooms[row][col] = min(distance, rooms[row][col])

 作业（并且 

if (row, col) in visited

 检查会跳过它）。