欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

走迷宫算法 用python实现

程序员文章站 2022-05-20 20:11:57
...

一个迷宫搜索的过程可以用python语言的算法来加以描述:

思路:穷举法。把所有的路都走了,总一条是对的。
首先老鼠不走回头路,它随便沿着一个方向一直走,遇到墙壁后换一个方向,直到没有路可以走,那么这条路就是死路。
然后,老鼠开始回退,一直回退到下一个路口,在沿着这条路一直走,以此类推,若存在到达出口的路,那么老鼠一定能走到出口。(因为最差的情况下,老鼠会把所有能走的路走一遍。)
用堆栈记录老鼠走过的路径,堆栈顶端为老鼠当前位置,若下一步有路可走,则压入堆栈,若下一步无路可走,则弹出顶端,一直弹出到有路可走为止。

if 上一格可走:
    把方格编号加入到堆栈
    往上走
    判断是否为出口
elif 下一格可走:
     把方格编号加入到堆栈
    往上走
    判断是否为出口
elif 左一格可走:
     把方格编号加入到堆栈
    往上走
    判断是否为出口
elif 右一格可走:
     把方格编号加入到堆栈
    往上走
    判断是否为出口
el色:
    从堆栈删除一个方格编号
    从堆栈中弹出一个方格编号
    往回走 

具体实现过程:(已知迷宫矩阵如下)

MAZE=[[1,1,1,1,1,1,1,1,1,1,1,1],\
      [1,0,0,0,1,1,1,1,1,1,1,1],\
      [1,1,1,0,1,1,0,0,0,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,0,0,0,0,1,1,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,1,1,1,0,1,1,0,1,1],\
      [1,1,0,0,0,0,0,0,1,0,0,1],\
      [1,1,1,1,1,1,1,1,1,1,1,1]]

1表示墙体,无法通过,0表示道路,可以通过。
老鼠的初始位置为[1,1](第2行第2列)
出口位置为[8,10] (第9行第11列)
利用堆栈数据机构,寻找迷宫的出口

代码如下:

class Node:#用类来实现链表
    def __init__(self):
        self.x=0
        self.y=0
        self.next=None
#用全局变量top来记录堆栈顶端的数据。压入数据时,新数据的指针指向top(旧顶端),top指向新数据,从而新数据出现在堆栈的顶端(LIFPO)
def push(x,y):
    global top
    new_node=Node()
    new_node.x=x
    new_node.y=y
    new_node.next=top
    top=new_node
    
def pop():
    global top
    top=top.next #弹出数据时,top直接指向top.next
#检查节点    
def check_point(x,y,ex,ey):
    if x==ex and y==ey:
        return 1
    else:
        return 0
#寻找下一节点    
def next_step(MAZE,ex,ey):
    a=top.x
    b=top.y
    ex=ex
    ey=ey
    if MAZE[a-1][b]==0:
        push(a-1,b)
        MAZE[a-1][b]=2
    elif MAZE[a][b-1]==0:
        push(a,b-1)
        MAZE[a][b-1]=2
    elif MAZE[a+1][b]==0:
        push(a+1,b)
        MAZE[a+1][b]=2
    elif MAZE[a][b+1]==0:
        push(a,b+1)
        MAZE[a][b+1]=2
    else:
        pop()
 #若老鼠走到了出口,那么停止算法,否则,老鼠会一直寻路。       
def find_road(MAZE,x,y,ex,ey):
    global top
    a=ex
    b=ey
    head=Node()
    head.x=x
    head.y=y
    head.next=None
    top=head
    while check_point(top.x,top.y,a,b)==0:
        next_step(MAZE,a,b)
        
    print('老鼠走过的路为:')
    for i in range(10):
        for j in range(12):
            print(MAZE[i][j],end='')
        print()
            
    
MAZE=[[1,1,1,1,1,1,1,1,1,1,1,1],\
      [1,0,0,0,1,1,1,1,1,1,1,1],\
      [1,1,1,0,1,1,0,0,0,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,0,0,0,0,1,1,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,0,1,1,0,1,1,0,1,1],\
      [1,1,1,1,1,1,0,1,1,0,1,1],\
      [1,1,0,0,0,0,0,0,1,0,0,1],\
      [1,1,1,1,1,1,1,1,1,1,1,1]]
x=1
y=1
ex=8
ey=10
print('='*20)
print('迷宫为:')
for i in range(10):
        for j in range(12):
            print(MAZE[i][j],end='')
        print()
print('='*20)
find_road(MAZE,x,y,ex,ey)
print('='*20)
while top!=None:
    MAZE[top.x][top.y]=3
    top=top.next
for i in range(10):
        for j in range(12):
            print(MAZE[i][j],end='')
        print()
while top!=None:
    MAZE[top.x][top.y]=3
    top=top.next
for i in range(10):
        for j in range(12):
            print(MAZE[i][j],end='')
        print()