|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- def dfs_maze(path, target):
- global paths
- maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]
- if path[-1] == target:
- paths.append(path)
- print(path)
- return
- for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
- node = [path[-1][0] + each[0], path[-1][1] + each[1]]
- if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
- path.append(node)
- dfs_maze(path, target)
- path.pop(-1)
- def main():
- dfs_maze([[0,0]], [4, 4])
- for each in paths:
- print(each)
- paths = []
- main()
复制代码
就是一个深搜解决迷宫最短路径的函数,path 是一个二维数组,储存已经走过的每一个点,target 是终点。在边界条件满足时,打印出来的路径是没问题的。但在深搜结束后,打印出来的 paths 是一堆[[0,0]]的二维数组,这是为何?
path分配的地址一样,每次做个切片 - def dfs_maze(path, target):
- global paths
- maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]
- if path[-1] == target:
- paths.append(path[:])
- print(path)
- return
- for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
- node = [path[-1][0] + each[0], path[-1][1] + each[1]]
- if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
- path.append(node)
- dfs_maze(path, target)
- path.pop(-1)
- def main():
- dfs_maze([[0,0]], [4, 4])
- for each in paths:
- print(each)
- paths = []
- main()
复制代码
|
|