[Python]迷宫问题

方法：深度优先搜索 又称回溯法；

思路：
从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点；
使用栈存储当前路径；

代码：

# 迷宫

maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]

dirs=[lambda x, y:(x+1, y),lambda x, y:(x-+1, y),lambda x, y:(x, y-1),lambda x, y:(x, y+1),]defmaze_path(x1,y1,x2,y2):
    stack=[]
    stack.append((x1,y1))while(len(stack)>0):
        curNode= stack[-1]#当前节点if curNode[0]== x2and curNode[1]== y2:# 走到终点了for pin stack:print('p: ',p)returnTruefordirin dirs:
            nextNode=dir(curNode[0],curNode[1])if maze[nextNode[0]][nextNode[1]]==0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]]=2#标记为已经走过breakelse:
            maze[curNode[0]][curNode[1]]=2
            stack.pop()else:returnFalse

a= maze_path(1,1,8,8)print(a)

另外一种方法实现
通过队列
不过感觉还是有点问题，我这个实现怎么都感觉不大对，奇怪了…

代码

# 迷宫from collectionsimport deque

maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]

dirs=[lambda x, y:(x+1, y),lambda x, y:(x-+1, y),lambda x, y:(x, y-1),lambda x, y:(x, y+1),]defprint_r(path):
    curNode= path[-1]
    realpath=[]print('--', curNode[2], curNode[2]==-1)while curNode[2]==-1:
        realpath.append(curNode[0:2])print('curNode[0:2] :', curNode[0:2])
        curNode= path[curNode[2]]
    realpath.append(curNode[0:2])# 起点
    realpath.reverse()# print('aaa',realpath)for nodein realpath:print('node: ', node)defmaze_path_queue(x1, y1, x2, y2):
    queue= deque()
    queue.append((x1, y1,-1))
    path=[]whilelen(queue)>0:
        curNode= queue.pop()# 当前节点
        path.append(curNode)if curNode[0]== x2and curNode[1]== y2:# 走到终点了# print('---',path)
            print_r(path)returnTruefordirin dirs:
            nextNode=dir(curNode[0], curNode[1])if maze[nextNode[0]][nextNode[1]]==0:
                queue.append((nextNode[0], nextNode[1],len(path)-1))# 后续节点进队
                maze[nextNode[0]][nextNode[1]]=2# 标记为已经走过else:print("no way")returnFalse


a= maze_path_queue(1,1,8,8)print(a)