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

jerryxjr1220

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

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

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

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

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

1. maze = [
   
2. #start (0,0)
   
3. [1 ,0, 1, 0, 0, 0],
   
4. [1, 1, 1, 1, 0, 1],
   
5. [0, 0, 1, 0, 1, 0],
   
6. [1, 0, 1, 0, 1, 1],#End (3,5)
   
7. [1, 1, 1, 1, 1, 1],
   
8. [0, 1, 0, 1, 0, 0],
   
9. [0, 1, 0, 1, 1, 1]]

复制代码

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

1. Done!
   
2. The right way marked "8"!
   
3. [8, 0, 1, 0, 0, 0]
   
4. [8, 8, 8, 1, 0, 1]
   
5. [0, 0, 8, 0, 1, 0]
   
6. [1, 0, 8, 0, 1, 8]
   
7. [1, 1, 8, 8, 8, 8]
   
8. [0, 1, 0, 1, 0, 0]
   
9. [0, 1, 0, 1, 1, 1]
   
10. [Finished in 0.4s]

复制代码

源代码：

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

另外一种探索解法：

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

吴三石

好评，受教了

逗逼小龙

滴滴

qywang

看看

qaz123765

看下

qaz123765

用的楼主的回溯法

1. maze = [
   
2. #start (0,0)
   
3. [1 ,0, 1, 0, 0, 0],
   
4. [1, 1, 1, 1, 0, 1],
   
5. [0, 0, 1, 0, 1, 0],
   
6. [1, 0, 1, 0, 1, 1],#End (3,5)
   
7. [1, 1, 1, 1, 1, 1],
   
8. [0, 1, 0, 1, 0, 0],
   
9. [0, 1, 0, 1, 1, 1]]
   
10. 
    
11. 
    
12. start=(0,0)
    
13. mov=[(-1,0),(1,0),(0,-1),(0,1)]
    
14. step=[(3,5)]
    
15. tr=step.pop()
    
16. a=[[0]*6 for i in range(7)]
    
17. b={}
    
18. m,n=0,0
    
19. #print(a)
    
20. while tr!=start:
    
21.     for i in mov:
    
22.         m=tr[0]+i[0]
    
23.         n=tr[1]+i[1]
    
24.    
    
25.         if 0<=m<7 and 0<=n<6 and maze[m][n]!=0 and a[m][n]!=1:
    
26.             step.append((m,n))
    
27.             b[(m,n)]=tr
    
28.             a[m][n]=1
    
29.             #print(step)
    
30.     tr=step.pop()
    
31. 
    
32. else:
    
33.     print('start!!')
    
34.     maze[0][0]='g'
    
35.     t=start
    
36.     while t!=(3,5):
    
37.         t=b[t]
    
38.         maze[t[0]][t[1]]='g'
    
39.         
    
40. for i in range(7):
    
41.     print(maze[i])
    
42. 
    

复制代码

qaz123765

探索法手机上看不到

2468085164

谢谢

weisuo

23546+

宸冬

66666666

dangyan199219

跟着学习一下，

haloyum

111

久疤K

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

1. 
   
2. import time
   
3. 
   
4. def ti(func):
   
5.     def call(*v):
   
6.         s = time.time()
   
7.         r = func(*v)
   
8.         t = time.time()
   
9.         print(func.__name__,t-s)
   
10.         return r
    
11.     return call
    
12. 
    
13. def _go(lss,now,end,res,ress):
    
14.     i,j = now
    
15.     if lss[i][j]==0 or now in res:
    
16.         return
    
17.     res.append(now)
    
18.     if now==end:
    
19.         ress.append(res)
    
20.         return
    
21.     tmp = []
    
22.     if i > 0:
    
23.         _go(lss,(i-1,j),end,res.copy(),ress)
    
24.     if i < len(lss)-1:
    
25.         _go(lss,(i+1,j),end,res.copy(),ress)
    
26.     if j > 0:
    
27.         _go(lss,(i,j-1),end,res.copy(),ress)
    
28.     if j < len(lss[i])-1:
    
29.         _go(lss,(i,j+1),end,res.copy(),ress)
    
30. 
    
31. def go(lss,start,end):
    
32.     ress = []
    
33.     _go(lss,start,end,[],ress)
    
34.     return ress
    
35. 
    
36. @ti
    
37. def fun():
    
38.     room = [[1 ,0, 1, 0, 0, 1 ,0, 1, 0, 0, 0],
    
39.             [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1],
    
40.             [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
    
41.             [1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1],
    
42.             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    
43.             [0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0],
    
44.             [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
    
45.             [1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1],
    
46.             [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
    
47.             [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
    
48.             [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
    
49.             [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
    
50.             [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
    
51.             [1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1],
    
52.             [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
    
53.             [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
    
54.             [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1],
    
55.             [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
    
56.             [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]]
    
57.     start = (0,0)
    
58.     end = (len(room)-1,len(room[-1])-1)
    
59.     ress = go(room,start,end)
    
60.     return ress
    
61. 
    
62. def main():
    
63.     ress = fun()
    
64.     print("total: " ,len(ress))
    
65.     print('None' if len(ress)==0 else ress[0])
    
66. 
    
67. if __name__ == "__main__":
    
68.     main()

复制代码

1. res:
   
2. fun 0.002000093460083008
   
3. total:  1
   
4. [(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

我试一下

阿拉雷

学习了