[python解迷宫问题] 字典+递归算法

jerryxjr1220

之前已经有好多帖子讨论过“迷宫问题”了，解法也各有千秋。

今天闲来无事又琢磨了一种“字典+递归的算法”。

解题思路：
利用字典把所有可能的路径列出来，利用递归算法逐层从字典中把路径找出来。

其他的看注解吧，写得很详细了。

举例：
迷宫为：（0为墙，1为路，起始（0，0），终点（3，5））

maze = [
 #start (0,0)
[1 ,0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],#End (3,5)
[1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 1, 1]]

程序输出：（正确路径用“8”标记出来了）

Done!
The right way marked "8"!
[8, 0, 1, 0, 0, 0]
[8, 8, 8, 1, 0, 1]
[0, 0, 8, 0, 1, 0]
[1, 0, 8, 0, 1, 8]
[1, 1, 8, 8, 8, 8]
[0, 1, 0, 1, 0, 0]
[0, 1, 0, 1, 1, 1]
[Finished in 0.4s]

源代码：

游客，如果您要查看本帖隐藏内容请回复

另外一种探索解法：

游客，如果您要查看本帖隐藏内容请回复

吴三石

好评，受教了

逗逼小龙

滴滴

qywang

看看

qaz123765

看下

qaz123765

用的楼主的回溯法

maze = [
#start (0,0)
[1 ,0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],#End (3,5)
[1, 1, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 1, 1]]


start=(0,0)
mov=[(-1,0),(1,0),(0,-1),(0,1)]
step=[(3,5)]
tr=step.pop()
a=[[0]*6 for i in range(7)]
b={}
m,n=0,0
#print(a)
while tr!=start:
    for i in mov:
        m=tr[0]+i[0]
        n=tr[1]+i[1]
    
        if 0<=m<7 and 0<=n<6 and maze[m][n]!=0 and a[m][n]!=1:
            step.append((m,n))
            b[(m,n)]=tr
            a[m][n]=1
            #print(step)
    tr=step.pop()

else:
    print('start!!')
    maze[0][0]='g'
    t=start
    while t!=(3,5):
        t=b[t]
        maze[t[0]][t[1]]='g'
        
for i in range(7):
    print(maze[i])

qaz123765

探索法手机上看不到

2468085164

谢谢

weisuo

23546+

宸冬

66666666

dangyan199219

跟着学习一下，

haloyum

111

久疤K

字典太大了，费时间，这个解法非常快

import time

def ti(func):
    def call(*v):
        s = time.time()
        r = func(*v)
        t = time.time()
        print(func.__name__,t-s)
        return r
    return call

def _go(lss,now,end,res,ress):
    i,j = now
    if lss[i][j]==0 or now in res:
        return
    res.append(now)
    if now==end:
        ress.append(res)
        return
    tmp = []
    if i > 0:
        _go(lss,(i-1,j),end,res.copy(),ress)
    if i < len(lss)-1:
        _go(lss,(i+1,j),end,res.copy(),ress)
    if j > 0:
        _go(lss,(i,j-1),end,res.copy(),ress)
    if j < len(lss[i])-1:
        _go(lss,(i,j+1),end,res.copy(),ress)

def go(lss,start,end):
    ress = []
    _go(lss,start,end,[],ress)
    return ress

@ti
def fun():
    room = [[1 ,0, 1, 0, 0, 1 ,0, 1, 0, 0, 0],
            [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1],
            [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
            [1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1],
            [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
            [0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
            [1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1],
            [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
            [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
            [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
            [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
            [1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1],
            [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
            [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
            [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1],
            [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
            [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]]
    start = (0,0)
    end = (len(room)-1,len(room[-1])-1)
    ress = go(room,start,end)
    return ress

def main():
    ress = fun()
    print("total: " ,len(ress))
    print('None' if len(ress)==0 else ress[0])

if __name__ == "__main__":
    main()

res:
fun 0.002000093460083008
total:  1
[(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (7, 6), (7, 7), (8, 7), (9, 7), (10, 7), (10, 8), (11, 8), (12, 8), (13, 8), (13, 7), (14, 7), (15, 7), (16, 7), (16, 8), (17, 8), (18, 8), (18, 9), (18, 10)]

jc42242

学习了，新手看看

唐永峰

真棒

Believen

666

thomas1994

支持支持！！！最近作业是这个

rindo419

感谢分享

Pannet

我试一下

阿拉雷

学习了