回溯找到迷宫出口。为什么我的函数总是 return True？

Question

我的代码成功地通过了迷宫中所有可能的路径...但它总是returnsTrue，即使只有真的如果满足某些条件（已到达迷宫的边缘），则更新。 看来我对范围有误解。这是我第一次使用全局关键字。

这是一些示例 input/output。上图是迷宫，两个数字是当前位置在迷宫中的(x,y)坐标。 'k'是起始位置，'#'是墙.

# # ## #
# #k#  #
# # # ##
# # #  #
#     ##
########
3 2
3 3
3 4
3 5
4 5
5 5
5 4
6 4
5 3
5 2
6 2
6 1
2 5
1 5
1 4
1 3
1 2
1 1
3 1
True

found = False
def find_start(maze):
    start = None
    for i in range(len(maze)):
        print(maze[i])
        for j in range(len(maze[i])):
            if maze[i][j] == 'k':
                if start == None:
                    start = (i, j)
                else:
                    raise "There should be no multiple Kates"
    if not start:
        raise "There should be one Kate"
    return start

def has_exit(maze):
    visited = [[False for _ in range(len(maze[i]))] for i in range(len(maze))]
    y, x = find_start(maze)
    def backtrack(maze, x, y):
        visited[y][x] = True
        print(x, y)
        if x == 0 or x == (len(maze[y]) - 1) or y == 0 or y == (len(maze) - 1) or x > len(maze[y+1]) - 1 or x > len(maze[y-1]) - 1: # This last condition is the hard one.
            print('Found edge')
            global found
            found = True
            return
        if maze[y][x+1] == ' ' and not visited[y][x+1]:
            backtrack(maze, x+1, y)
        if maze[y][x-1] == ' ' and not visited[y][x-1]:
            backtrack(maze, x-1, y)
        if maze[y+1][x] == ' ' and not visited[y+1][x]:
            backtrack(maze, x, y+1)
        if maze[y-1][x] == ' ' and not visited[y-1][x]:
            backtrack(maze, x, y-1)
        
    backtrack(maze, x, y)
    if found:
        print(found)
        return True
    else:
        print(found)
        return False

Answer 1

您还没有为您的代码提供进一步调试的起点。

然而 Python 中全局关键字的基本规则是：

当我们在函数内部创建一个变量时，它默认是局部的。
当我们在函数外定义一个变量时，它是全局的 default.You 不必使用全局关键字。
我们使用全局关键字在函数内读写全局变量。
使用全局函数外的关键字无效。

Source - 在此来源中可以找到更多示例

Answer 2

唯一给 found 赋值的地方是第一次通过代码 =False 然后每当代码命中 backtrack 时，它就会赋值 True。对于您的问题重要的是，您永远不会重置 found，因此一旦设置为 True 一次，它就永远不会重置。因为你在所有可能的路径上递归，你最终会碰到一个边缘，所以 found=True 最终对于任何运行.

我同意关于使用 return 函数值的其他建议，但在这里您只需要适当地重置状态以进行递归搜索。

回溯找到迷宫出口。为什么我的函数总是 return True？

Backtracking to find the maze exit. Why does my function always return True?

python

scope

global

recursive-backtracking