广度优先遍历简称为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)