时间戳

首页 > 解决方案 > Python3多次使用相同的输入运行相同的函数，但每次产生不同的输出

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

问题描述

我目前正在尝试用 python 解决一个简单版本的检查器。具体来说，我正在尝试解决 USACO 2008 年 12 月铜牌比赛中的“跳棋”问题。（问题链接）

我的想法是在每个国王的位置上运行递归 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()))

标签： pythonpython-3.xpython-3.7depth-first-search

解决方案

.copy()list 方法仅适用于列表的一个“层” 。由于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(). 您将需要制作某种形式的“双重”副本。

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

>>> 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]]

推荐阅读