Python3实现USACO铜组跳棋题DFS同输入多次调用输出不一致排查

• 使用Python3.7实现USACO 2008年12月铜组checkers题的简化版求解，核心思路是对棋盘上每枚王棋（K）的位置执行递归DFS遍历。
• 异常表现：传入完全相同的参数连续多次调用DFS函数时，仅第一次能得到正确输出，后续调用结果与第一次存在明显差异。
• 调用逻辑说明：三次调用时均显式传入grid.copy()作为棋盘副本、空列表作为初始路径、空集合作为初始访问记录，从代码层面看入参完全一致。

相关核心代码 #

DFS函数实现 #

def dfs(x, y, n, graph, path, count, visited):
    if str([x+1, y+1]) not in visited:
        visited.add(str([x+1, y+1]))
        if count == 0:
            path += [[x+1, y+1]]
            return path
        if x < 0 or y < 0 or x > n or y > n:
            return path
        path += [[x+1, y+1]]
        try:
            if graph[x+1][y+1] == "o":
                graph[x+1][y+1] = "+"
                return dfs(x+2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x+1][y-1] == "o":
                graph[x+1][y-1] = "+"
                return dfs(x+2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y+1] == "o":
                graph[x-1][y+1] = "+"
                return dfs(x-2, y+2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        try:
            if graph[x-1][y-1] == "o":
                graph[x-1][y-1] = "+"
                return dfs(x-2, y-2, n, graph, path, count-1, visited)
        except IndexError as e: pass
        return path

函数调用代码 #

print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))
print(dfs(7, 2, n, grid.copy(), [], count, set()))

异常根因 #

• 浅拷贝引发的棋盘状态残留污染：grid是逐行通过list(input().rstrip())生成的二维列表，对其直接调用.copy()属于浅拷贝操作，仅会复制最外层的行容器，行内部的字符列表不会被独立复制。第一次DFS执行时，对传入的graph对象做的graph[行索引][列索引] = "+"修改，会直接写入原始grid内部的行列表，导致后续两次调用时，基于被污染的原始grid复制出的棋盘已经不是初始状态，自然无法复现第一次的正确输出。
• 边界判断顺序逻辑错误：代码在完成当前位置的路径添加、甚至执行修改棋盘棋子状态的操作之后，才判断坐标是否越界，一旦递归走到非法坐标，之前对棋盘的修改已经生效，进一步放大了浅拷贝带来的状态污染影响。
• 访问记录逻辑错位：visited集合仅记录下一跳的位置，没有记录递归入口的初始K点位置，且没有在路径回溯时移除已记录的位置，会提前截断所有合法的遍历分支。

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