Python解决走迷宫问题算法示例

时间:2022-11-10 14:48:37

本文实例讲述了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代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# -*- coding:utf-8 -*-
def init():
  global graph
  graph.append([-1-1, -1, -1, -1, -1-1])
  graph.append([-10, 0, -1, 0, 0-1])
  graph.append([-10, -1, 0, 0, 0-1])
  graph.append([-10, -1, 0, -1, -1-1])
  graph.append([-10, -1, 0, 0, 0-1])
  graph.append([-10, 0, 0, -1, 0-1])
  graph.append([-10, 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])

运行结果:

(1, 1, 0)
(1, 2, 1)
(2, 1, 1)
(3, 1, 2)
(4, 1, 3)
(5, 1, 4)
(5, 2, 5)
(5, 3, 6)
(4, 3, 7)
(3, 3, 8)
(2, 3, 9)
(2, 4, 10)
(1, 4, 11)
(1, 5, 12)
(2, 5, 13)
(2, 5, 11)
(4, 4, 8)
(4, 5, 9)
(5, 5, 10)
(6, 5, 11)
(6, 4, 12)
(6, 3, 13)
(6, 2, 14)
(6, 1, 15)
(6, 3, 7)
(6, 2, 8)
(6, 1, 9)
(6, 4, 8)
(6, 5, 9)
(6, 2, 6)
(6, 1, 7)
(6, 1, 5)
12

希望本文所述对大家Python程序设计有所帮助。

原文链接:http://www.cnblogs.com/Lin-Yi/p/7355428.html