# -*- coding: utf-8 -*-

'''
Python程序员面试算法宝典---解题总结: 第4章 数组 4.21 如何求解迷宫问题

题目:
给定一个大小为N*N的迷宫，一只老鼠需要从迷宫的左上角(
对应矩阵的[0][0])走到迷宫的右下角(对应矩阵的[N-1][N-1])，
老鼠只能向两方向移动:向右或向下。在迷宫中，0表示没有路
(是死胡同)，1表示有路。例如: 给定下面的迷宫:
1   0   0   0
1   1   0   1
0   1   0   0
1   1   1   1
途中标粗的路径就是一条合理的路径。
请给出算法来找到这么一条合理路径。

分析:
应该是搜索问题。搜索分为深度优先搜索和广度优先搜索。
广度优先搜索用于求解: 最优值问题
深度优先搜索用于求解: 是否有解问题，不具有最优特性
这道题目应该用深度优先搜索做(这里应该是回溯)。
搜索停止的条件为:
i=N-1, j=N-1

广度优先搜索算法的主要步骤如下:
判断当前位置如果无效，则直接返回；
如果当前位置就是待查找位置，返回结果；
否则，根据当前位置，构造下一个查找的位置，
递归对下一个查找位置进行搜索。

如何保存路径。
可以用一个栈，

关键:
1 我缺少了一个回溯的方式
设置已经访问过的标记为1，没有访问过的为0
回溯算法的模板为:
找到，则打印结果
设置标记
递归
清除标记
    ......
    if i == rowLen - 1 and j == colLen - 1:
        path[i][j] = 1
        return True
    path[i][j] = 1
    rightResult = bfsMaze(maze, i + 1, j, rowLen, colLen, path)
    if rightResult:
        return True
    downResult = bfsMaze(maze, i, j + 1, rowLen, colLen, path)
    if downResult:
        return True
    path[i][j] = 0
    ......

2 我之所以没有想到
是忘记了回溯法实际就是一种高级递归，但是有状态，
通过: 找到目标打印，设置标记，递归，清除标记4步骤实现
参考:
Python程序员面试算法宝典
'''


def bfsMaze(maze, i, j, rowLen, colLen, path):
    # 如果找到所求的点
    if i == rowLen - 1 and j == colLen - 1:
        path[i][j] = 1
        return True
    if not maze:
        return False
    if i < 0 or i >= rowLen or j < 0 or j >= colLen:
        return False
    # 如果当前不能行走，即对应元素的值为0，返回False
    if 0 == maze[i][j]:
        return False
    # 回溯: 设置标记，表示该位置已经访问过
    path[i][j] = 1

    # 构造所有下一个位置
    # 向右是: i += 1, j不变；
    # 向下是: i不变， j += 1
    rightResult = bfsMaze(maze, i + 1, j, rowLen, colLen, path)
    if rightResult:
        return True
    downResult = bfsMaze(maze, i, j + 1, rowLen, colLen, path)
    if downResult:
        return True
    # 说明路径不可行，清除之前设置的标记
    path[i][j] = 0
    return False


def process():
    maze = [
        [1, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 1, 0, 0],
        [1, 1, 1, 1]
    ]
    rowLen = len(maze)
    colLen = len(maze[0])
    # 记录
    path = [[0] * colLen for i in range(rowLen)]
    i = 0
    j = 0
    result = bfsMaze(maze, i, j, rowLen, colLen, path)
    if result:
        print "有路线走出迷宫，路线下标如下(横坐标，纵坐标):"
        for array in path:
            info = ""
            for value in array:
                info += " " + str(value)
            print info
    else:
        print "没有路线走出迷宫"
    # if result:
    #     print "有路线走出迷宫，路线下标如下(横坐标，纵坐标):"
    #     info = [str(value)for value in reversed(path)]
    #     print ",".join(info)
    # else:
    #     print "没有路线走出迷宫"


if __name__ == "__main__":
    process()