HashSet中clear()与copy()的差异：DFS场景下的疑问解析

问题背景 #

我在解决Walls and Gates问题时，先写出了如下DFS解法，但部分测试用例失败：

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)

之后我修改代码，传递HashSet的副本后通过了所有测试用例：

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()能解决问题？我知道copy()传递的是副本而非引用，但原代码中每次遍历前都会执行visited.clear()，这难道不是一样的效果吗？DFS并非并行执行，为何需要传递副本？

解答 #

核心问题出在原代码的visited集合是全局共享的，DFS递归的不同分支会互相修改这个集合，导致后续遍历路径出错。

具体来说：

• 原代码里，每次从门（值为0的格子）开始遍历前执行visited.clear()，这确实能清空集合，但递归过程中所有分支共享同一个visited。比如从门出发先递归向下走，把路径上的格子加入visited；回溯后走向右的分支时，visited里还保留着向下路径的格子标记，这会导致向右分支无法访问那些本来可达、却被其他分支标记为已访问的格子——但实际上，不同递归路径的已访问状态应该是独立的，不能互相干扰。
• 修改后的代码，每次递归调用都传递visited.copy()，相当于给每个递归分支创建了独立的已访问集合。每个分支只会标记自己路径上的格子，不会影响其他分支的遍历。比如向下走的分支有自己的visited，向右走的分支也有独立的副本，两者互不干扰，这样就能保证每个路径都能正确遍历所有可达的非墙格子，不会因为其他分支的标记而漏掉需要更新的房间距离。

举个简单例子：假设某个房间可以从同一个门的两条不同路径到达，第一条路径的距离是3，第二条是2。原代码的全局visited会在第一条路径走过这个房间后标记为已访问，导致第二条路径即使距离更近，也无法进入该房间更新距离；而用副本的话，第二条路径的visited里没有这个房间的标记，就能正常进去检查并更新为更小的距离。

另外，visited.clear()只是在每次门的遍历开始时清空，但递归过程中共享集合的修改是持续的，这和每个递归分支用独立副本完全是两回事——前者是全局共享，分支互相污染；后者是分支各自独立，互不影响。

内容的提问来源于stack exchange，提问作者user1010101