题解 | #迷宫问题#

解题思路：
1.广度优先搜索
2. 细节： 移动方向，走过标记，前缀记录，终点判断
3. 输出结果，采用栈

# -*- coding: utf-8 -*-
# 开发者    : QSheng
# 代码文件  : HJ43 迷宫问题.py
# 创建时间  : 2021/7/27 17:06

class Solution:
    def solve(self, matrix, row, col):
        dir_list = [[-1,0], [1,0], [0,1], [0,-1]]                       # 四个方向
        use_flag = [[0 for i in range(col)] for j in range(row)]        # 走过的标记
        pre_dict = dict()       # 记录每个点的前置
        queue = list()          # 队列
        queue.append((0, 0))    # 入队列
        use_flag[0][0] = 1      # 标记
        if_find = False
        while len(queue) > 0 and if_find is False:
            # 出队列
            curr_node = queue.pop(0)

            # 四个方向
            for idx in range(len(dir_list)):
                new_i, new_j = dir_list[idx][0] + curr_node[0], dir_list[idx][1] + curr_node[1]
                # 坐标合法
                if 0 <= new_i < row and 0 <= new_j < col:
                    if use_flag[new_i][new_j] == 1: # 已经使用过该点，就继续循环
                        continue
                    if matrix[new_i][new_j] == 1:   # 该节点行不通
                        continue
                    pre_dict[(new_i, new_j)] = curr_node    # 记录前缀
                    queue.append((new_i, new_j))            # 加入队列
                    use_flag[new_i][new_j] = 1              # 标记

                    if new_i == row - 1 and new_j == col - 1: # 找到终点
                        if_find = True
                        break
        rnt = list()
        rnt.append((row-1, col-1))
        while True:
            last_node = pre_dict[rnt[-1]]
            rnt.append(last_node)
            if last_node == (0, 0):
                break

        ans = ""
        while len(rnt) > 1:
            note_tmp = rnt.pop()
            ans += "({},{})\n".format(note_tmp[0], note_tmp[1])
        note_tmp = rnt.pop()
        ans += "({},{})".format(note_tmp[0], note_tmp[1])

        return ans

import sys

if __name__ == '__main__':
    is_IDE = False
    if is_IDE:
        fr = open("data/HJ43.txt", "r", encoding="utf-8")
    else:
        fr = sys.stdin

    while True:
        line = fr.readline().strip()
        if line == "":
            break
        row_num, col_num = int(line.split(" ")[0]), int(line.split(" ")[1])
        matrix = list()
        for i in range(row_num):
            line_tmp = fr.readline().strip().split(" ")
            matrix.append([int(i) for i in line_tmp])
        print(Solution().solve(matrix, row_num, col_num))


    if is_IDE:
        fr.close()