大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本文实例讲述了Python解决走迷宫问题算法。分享给大家供大家参考,具体如下:
站在用户的角度思考问题,与客户深入沟通,找到阳曲网站设计与阳曲网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:网站建设、成都网站建设、企业官网、英文网站、手机端网站、网站推广、域名与空间、网络空间、企业邮箱。业务覆盖阳曲地区。问题:
输入n * m 的二维数组 表示一个迷宫
数字0表示障碍 1表示能通行
移动到相邻单元格用1步
思路:
深度优先遍历,到达每一个点,记录从起点到达每一个点的最短步数
初始化案例:
1 1 0 1 1
1 0 1 1 1
1 0 1 0 0
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1
1 把图周围加上一圈-1 , 在深度优先遍历的时候防止出界
2 把所有障碍改成-1,把能走的地方改成0
3 每次遍历经历某个点的时候,如果当前节点值是0 把花费的步数存到节点里
如果当前节点值是-1 代表是障碍 不遍历它
如果走到当前节点花费的步数比里面存的小,就修改它
修改后的图:
-1 -1 -1 -1 -1 -1 -1
-1 0 0 -1 0 0 -1
-1 0 -1 0 0 0 -1
-1 0 -1 0 -1 -1 -1
-1 0 -1 0 0 0 -1
-1 0 0 0 -1 0 -1
-1 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1
外周的-1 是遍历的时候防止出界的
默认从左上角的点是入口 右上角的点是出口
Python代码:
# -*- coding:utf-8 -*- def init(): global graph graph.append([-1, -1, -1, -1, -1, -1, -1]) graph.append([-1, 0, 0, -1, 0, 0, -1]) graph.append([-1, 0, -1, 0, 0, 0, -1]) graph.append([-1, 0, -1, 0, -1, -1, -1]) graph.append([-1, 0, -1, 0, 0, 0, -1]) graph.append([-1, 0, 0, 0, -1, 0, -1]) graph.append([-1, 0, 0, 0, 0, 0, -1]) graph.append([-1, -1, -1, -1, -1, -1, -1]) #深度优先遍历 def deepFirstSearch( steps , x, y ): global graph current_step = steps + 1 print(x, y, current_step ) graph[x][y] = current_step next_step = current_step + 1 ''' 遍历周围4个点: 如果周围节点不是-1 说明 不是障碍 在此基础上: 里面是0 说明没遍历过 我们把它修改成当前所在位置步数加1 里面比当前的next_step大 说明不是最优方案 就修改它 里面比当前next_step说明当前不是最优方案,不修改 ''' if not(x-1== 1 and y==1) and graph[x-1][y] != -1 and ( graph[x-1][y]>next_step or graph[x-1][y] ==0 ) : #左 deepFirstSearch(current_step, x-1 , y ) if not(x == 1 and y-1==1) and graph[x][y-1] != -1 and ( graph[x][y-1]>next_step or graph[x][y-1] ==0 ) : #上 deepFirstSearch(current_step, x , y-1 ) if not(x == 1 and y+1==1) and graph[x][y+1] != -1 and ( graph[x][y+1]>next_step or graph[x][y+1]==0 ) : #下 deepFirstSearch(current_step, x , y+1 ) if not(x+1== 1 and y==1) and graph[x+1][y] != -1 and ( graph[x+1][y]>next_step or graph[x+1][y]==0 ) : #右 deepFirstSearch(current_step, x+1 , y ) if __name__ == "__main__": graph = [] init() deepFirstSearch(-1,1,1) print(graph[1][5])