Python3 运行多次使用相同输入但每次产生不同输出的相同函数

Question

我目前正在尝试使用 python 解决一个简单版本的西洋跳棋。具体来说，我正在尝试解决 USACO 2008 年 12 月铜牌竞赛的“跳棋”问题。 (Problem Link)

我的想法是运行一个关于每个国王位置的递归 dfs 函数。但是，我的 dfs 函数遇到了一些问题。当我多次运行我的 dfs 函数时，该函数产生不同的输出，即使使用相同的参数。具体来说，它只会在第一时间产生正确的输出。我不知道发生了什么，任何帮助将不胜感激，谢谢！（我使用的是 Python 3.7）

这是我的 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

这是我调用 dfs 函数的方式：

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()))

这是我得到的输出：

这是我的完整代码：

n = int(input())
grid = []
for i in range(n):
    grid.append(list(input().rstrip()))
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

count = 0
Ks = []
for x in range(n):
    for y in range(n):
        if grid[x][y] == "K":
            Ks.append([x, y])
        if grid[x][y] == "o":
            count += 1
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()))

Answer 1

.copy() 列表方法仅适用于列表的一个“层”。由于grid是一个列表的列表，如果你改变副本，原来的仍然会改变。

例如，在 Python 控制台中尝试

>>> a = [[1,2,3], [4,5,6], [7,8,9]]
>>> b = a.copy()
>>> b
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> b[0][0] = 5
>>> a
[[5, 2, 3], [4, 5, 6], [7, 8, 9]]

您看到 a 已经改变，尽管 b 被设置为 a.copy()。您将需要制作某种形式的“双重”副本。

或者，使用 copy 模块中的 deepcopy 函数：

>>> from copy import deepcopy
>>> a = [[1,2,3], [4,5,6], [7,8,9]]
>>> b = deepcopy(a)
>>> b[0][0] = 5
>>> a
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Python3 运行多次使用相同输入但每次产生不同输出的相同函数

Python3 running the same function with the same input many times but producing different outputs every time

python

depth-first-search

python-3.x

python-3.7

Python3 运行 多次使用相同输入但每次产生不同输出的相同函数

Python3 running the same function with the same input many times but producing different outputs every time

python

depth-first-search

python-3.x

python-3.7

Python3 运行多次使用相同输入但每次产生不同输出的相同函数