利用广度优先遍历搜索迷宫的python源代码

广度优先遍历简称为DFS，是数据结构中比较常用的一个算法，主要原理是采用队列先进先出的规则，一层一层的访问图的节点。而迷宫问题接近与遍历，但是不同于遍历，主要考虑是采用栈的形式标记路径，并对当前节点和死胡同分别标记为2和3，对死胡同的节点弹出栈，这样循环最终会找到一个路径。当然，存在一个问题就是不一定是最优的路径。

'''
Title:广度优先遍历探索迷宫
Date: 2018-04-18
Author:Jackie
Commont:
1、使用栈stack保存路径
2、采用广度优先遍历，将当前节点（栈的顶点）可用的临近节点全部压栈，并标记为2
3、对于发现死胡同时，将当前节点弹出栈，并标记为3
4、不需要使用队列，因为队列主要实现遍历，而不是最优化
'''

from collections import deque

matrix = [
[0, 1, 0, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]

# dfs function
def dfs_fun(matrix, start, end):
stack = []
stack.append(start)
x, y = start
matrix[x][y] =2
forward = True
while stack:
pos = stack[-1]
if pos == end:
print("Had find last path")
return stack
xPos, yPos = pos
forward = False
if yPos+1 < len(matrix):
if matrix[xPos][yPos+1] ==0:
stack.append((xPos, yPos+1))
matrix[xPos][yPos+1] =2
forward = True
if xPos+1 < len(matrix) :
if matrix[xPos+1][yPos] ==0:
stack.append((xPos+1, yPos))
matrix[xPos+1][yPos] =2
forward = True
if xPos-1 >=0 :
if matrix[xPos-1][yPos] ==0:
stack.append((xPos-1, yPos))
matrix[xPos-1][yPos] =2
forward = True
if yPos-1>=0:
if matrix[xPos][yPos-1] ==0:
stack.append((xPos, yPos-1))
matrix[xPos][yPos-1] =2
forward = True
# bad road
if not forward:
x, y = stack.pop()
matrix[xPos][yPos] = 3
return False


if __name__ == '__main__':
result = dfs_fun(matrix, (0,0), (4,4))
print(result)