jerryxjr1220 发表于 2017-1-1 20:27:43

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

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

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

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

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

举例：
迷宫为：（0为墙，1为路，起始（0，0），终点（3，5））
maze = [
#start (0,0)
,
,
,
,#End (3,5)
,
,
]

程序输出：（正确路径用“8”标记出来了）
Done!
The right way marked "8"!









源代码：
**** Hidden Message *****

另外一种探索解法：
**** Hidden Message *****

吴三石 发表于 2017-1-1 21:11:48

好评，受教了

逗逼小龙 发表于 2017-2-13 19:42:12

滴滴

qywang 发表于 2017-2-16 15:33:22

看看

qaz123765 发表于 2017-6-23 07:41:25

看下

qaz123765 发表于 2017-6-23 13:15:34

本帖最后由 qaz123765 于 2017-6-23 13:29 编辑

用的楼主的回溯法
maze = [
#start (0,0)
,
,
,
,#End (3,5)
,
,
]


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

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

qaz123765 发表于 2017-6-23 13:27:09

探索法手机上看不到

2468085164 发表于 2017-6-30 22:16:30

谢谢

weisuo 发表于 2017-7-15 22:38:13

23546+

宸冬 发表于 2018-6-25 16:07:12

66666666

dangyan199219 发表于 2018-6-26 13:15:40

跟着学习一下，

haloyum 发表于 2018-7-4 22:48:49

111

久疤K 发表于 2018-7-5 14:04:53

本帖最后由 久疤K 于 2018-7-5 14:07 编辑

字典太大了，费时间，这个解法非常快
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==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)-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 = [,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ,
            ]
    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)

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 发表于 2018-7-20 11:16:08

学习了，新手看看

唐永峰 发表于 2018-8-5 09:43:07

真棒

Believen 发表于 2018-12-31 21:06:33

666

thomas1994 发表于 2019-4-16 14:27:06

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

rindo419 发表于 2019-4-16 15:09:19

感谢分享

Pannet 发表于 2019-6-3 14:41:00

我试一下

阿拉雷 发表于 2019-6-7 19:53:41

学习了
页: [1] 2
查看完整版本: [python解迷宫问题] 字典+递归算法