QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码
查看: 741|回复: 8

[技术交流] [python解迷宫问题] 字典+递归算法

[复制链接]
最佳答案
53 
累计签到:348 天
连续签到:2 天
发表于 2017-1-1 20:27:43 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

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

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

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

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

举例:
迷宫为:(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]
复制代码


源代码:
游客,如果您要查看本帖隐藏内容请回复


另外一种探索解法:
游客,如果您要查看本帖隐藏内容请回复
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:23 天
连续签到:1 天
发表于 2017-1-1 21:11:48 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-2-13 19:42:12 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:18 天
连续签到:2 天
发表于 2017-2-16 15:33:22 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-6-23 07:41:25 From FishC Mobile | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-6-23 13:15:34 From FishC Mobile | 显示全部楼层
本帖最后由 qaz123765 于 2017-6-23 13:29 编辑

用的楼主的回溯法
  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. start=(0,0)
  11. mov=[(-1,0),(1,0),(0,-1),(0,1)]
  12. step=[(3,5)]
  13. tr=step.pop()
  14. a=[[0]*6 for i in range(7)]
  15. b={}
  16. m,n=0,0
  17. #print(a)
  18. while tr!=start:
  19.     for i in mov:
  20.         m=tr[0]+i[0]
  21.         n=tr[1]+i[1]
  22.    
  23.         if 0<=m<7 and 0<=n<6 and maze[m][n]!=0 and a[m][n]!=1:
  24.             step.append((m,n))
  25.             b[(m,n)]=tr
  26.             a[m][n]=1
  27.             #print(step)
  28.     tr=step.pop()

  29. else:
  30.     print('start!!')
  31.     maze[0][0]='g'
  32.     t=start
  33.     while t!=(3,5):
  34.         t=b[t]
  35.         maze[t[0]][t[1]]='g'
  36.         
  37. for i in range(7):
  38.     print(maze[i])

复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-6-23 13:27:09 From FishC Mobile | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-6-30 22:16:30 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:19 天
连续签到:1 天
发表于 2017-7-15 22:38:13 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /3 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2017-11-19 06:59

快速回复 返回顶部 返回列表