python 广度优先搜索 亮点在于最后判断最短路径

先看岛屿的最大面积这道题目，再来做迷宫题

first_row = list(map(int, input().strip().split()))
rows = first_row[0]
cols = first_row[1]
p = first_row[2]
maze = [list(map(int, input().strip().split())) for _ in range(rows)]
# 把体力值放到栈中，便于后续操作
stack = [[0, 0, p]]
trace = []
# 当栈不为空的时候，说明还有格子没有被遍历到，也就是说路径还没走到头
while stack:
    cur_i, cur_j, value = stack.pop(0)
    # 判断边界值条件，判断是否是障碍物，如果不满足条件，就跳过下面的代码，返回到出栈过程
    if cur_i < 0 or cur_i > rows - 1 or cur_j < 0 or cur_j > cols - 1 or maze[cur_i][cur_j] != 1:
        continue
    # 用trace列表是为了获得轨迹，这个轨迹就是通往终点过程中格子值为1的坐标，里面可能会有很多其它不必要的坐标
    trace.append([cur_i, cur_j, value])
    # 将走过的格子值置为0，防止重复计算，那就真的走不出去了
    maze[cur_i][cur_j] = 0
    # 如果value<0，说明体力值不够了，那直接跳出循环
    if value < 0:
        print("Can not escape!")
        break
    # 如果成功到达终点，那么就要对trace处理了，找出最短路径是什么
    if cur_i == 0 and cur_j == cols - 1:
        # 先取中trace中每个元素的坐标（即前两个元素），组成一个新列表
        trace_temp = [ele[0:2] for ele in trace]
        # 将新列表逆序排列，为什么这么做？是因为我在找最短路径的时候注意到一个规律
        # 最短路径上的任一点和该点前后元素的横纵坐标是满足一个条件的，这个条件就是下面代码中的if语句
        # 不过从起点开始用这个规律会出问题，因为点可能会走到死胡同里而到不了终点
        # 但是从终点开始用这个规律就一定没问题
        trace_temp.reverse()
        s_trace = [trace_temp[0]]
        # id0是s_trace的索引，id1是trace_temp的索引
        id0 = 0
        id1 = 1
        while id1 < len(trace_temp):
            ele = s_trace[id0]
            ele_next = trace_temp[id1]
            if (ele_next[0] == ele[0] + 1 and ele[1] == ele_next[1]) or (
                    ele_next[0] == ele[0] - 1 and ele[1] == ele_next[1]) or (
                    ele_next[1] == ele[1] + 1 and ele[0] == ele_next[0]) or (
                    ele_next[1] == ele[1] - 1 and ele[0] == ele_next[0]):
                s_trace.append(ele_next)
                id0 += 1
            id1 += 1
        # 生成了s_trace之后再逆序排列
        s_trace.reverse()
        # 程序输出是字符串，而且是没有空格的字符串，值得注意
        print(str(s_trace)[1:-1].replace(' ',''))
        break
    # 广度优先搜索，
    for di, dj, dvalue in [[0, 1, -1], [0, -1, -1], [-1, 0, -3], [1, 0, 0]]:
        # 每次移动之前的初始体力值都是当前位置的体力值，这个值得注意
        value0 = value
        next_i, next_j = cur_i + di, cur_j + dj
        # 在小青蛙移动的时候也要对体力值进行操作
        value0 += dvalue
        stack.append([next_i, next_j, value0])