首页 > 代码库 > 走迷宫问题
走迷宫问题
输入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 是遍历的时候防止出界的
默认从左上角的点是入口 右上角的点是出口
1 def init():
2 global graph
3 graph.append([-1, -1, -1, -1, -1, -1, -1])
4
5 graph.append([-1, 0, 0, -1, 0, 0, -1])
6 graph.append([-1, 0, -1, 0, 0, 0, -1])
7 graph.append([-1, 0, -1, 0, -1, -1, -1])
8 graph.append([-1, 0, -1, 0, 0, 0, -1])
9 graph.append([-1, 0, 0, 0, -1, 0, -1])
10 graph.append([-1, 0, 0, 0, 0, 0, -1])
11
12 graph.append([-1, -1, -1, -1, -1, -1, -1])
13
14 #深度优先遍历
15 def deepFirstSearch( steps , x, y ):
16
17 global graph
18 current_step = steps + 1
19 print(x, y, current_step )
20
21 graph[x][y] = current_step
22 next_step = current_step + 1
23 ‘‘‘
24 遍历周围8个节点:
25 1如果周围节点不是-1 说明 不是障碍 在此基础上：
26 里面是0 说明没遍历过
27 里面比当前的next_step大 说明不是最优方案
28 满足以上 就修改它
29 ‘‘‘
30
31 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 ) : #左
32 deepFirstSearch(current_step, x-1 , y )
33 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 ) : #上
34 deepFirstSearch(current_step, x , y-1 )
35 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 ) : #下
36 deepFirstSearch(current_step, x , y+1 )
37 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 ) : #右
38 deepFirstSearch(current_step, x+1 , y )
39
40
41
42
43 if __name__ == "__main__":
44 graph = []
45 init()
46
47 deepFirstSearch(-1,1,1)
48 print(graph[1][5])
走迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。