题解 | #迷宫问题#

# BFS搜索，同时返回路径
#=================================================================================
r = 5 
c = 5
maze = [[0, 1, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 1, 0]]
#print(' '.join(map(str,t)))

xy0 = [0,0,-1]
xy1 = [r-1,c-1,-1]
MOV = [[1,0],[0,1],[-1,0],[0,-1]]                    # 四个方向移动一格
#---------------------------------------------------------------------------------
# Path中的每一行存有路径坐标点，第三个值保存上一个节点的list索引，从0开始
def road(visited):
    shortest_path = []
    shortest_path.append(visited[-1][:-1])
    t = visited[-1][-1]
    while t!=-1:
        shortest_path.append(visited[t][:-1])
        t = visited[t][-1]
    return shortest_path[::-1]

#---------------------------------------------------------------------------------
# BFS（宽度优先搜索）解迷宫问题
def bfs(xy0):

    queue = [xy0]                                    # 开始点进入队列
    visited = []                                     # 记录所有访问过的点，以及每一个点前一个节点索引
    k = 0

    while queue:                                     # 队列不为空即运行
        xy = queue.pop()                             # 队列中取出一个新坐标点
        maze[xy[0]][xy[1]] = 9                       # 开始点标记为已访问值9
        visited.insert(k, xy)                        # 相当于path.append(xy),这样写更清楚

        if xy[0] == xy1[0] and xy[1] == xy1[1]:
            shortest_path = road(visited)            # 到达终点时，反向寻找来时路径
            return shortest_path       

        for mov in MOV:                              # 四个方向移动
            xy_new = [xy[0]+mov[0], xy[1]+mov[1]]    # 移动后的新坐标
            if 0<=xy_new[0]<=r-1 and 0<=xy_new[1]<=c-1 and maze[xy_new[0]][xy_new[1]] == 0:     # 坐标有效且没有被访问过
                xy_new = [xy_new[0],xy_new[1],k]     # 将前一个点的索引加入坐标之后（用于反向寻找路径）
                queue.insert(0, xy_new)              # 新坐标不为终点，新坐标入队列,
        k += 1                    

#---------------------------------------------------------------------------------
shortest_path = bfs(xy0)
if shortest_path:
     for i in shortest_path:
        print('('+str(i[0])+','+str(i[1])+')')
else:
    print('none')
#---------------------------------------------------------------------------------


# DFS搜索，返回路径
#=================================================================================
r = 5 
c = 5
maze = [[0, 1, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 1, 0]]
#print(' '.join(map(str,t)))

xy0 = [0,0]
xy1 = [r-1,c-1]
MOV = [[1,0],[0,1],[-1,0],[0,-1]]                    # 四个方向移动一格
#---------------------------------------------------------------------------------
# 递归调用dfs(xy_new, res+[xy_new])时， res+[xy_new]实际保存了不断增长的路径

res = [xy0]
def dfs(xy0, res):                                          # xy0为当前搜索点，res保存了当前点历史路径

    maze[xy0[0]][xy0[1]] = 9

    if xy0[0] == xy1[0] and xy0[1] == xy1[1]:
        shortest_path = res
        return shortest_path                                # 到达终点时读取res返回最路径

    for mov in MOV:                                         # 四个方向移动
        xy_new = [xy0[0]+mov[0], xy0[1]+mov[1]]             # 移动后的新坐标
        if 0<=xy_new[0]<=r-1 and 0<=xy_new[1]<=c-1 and maze[xy_new[0]][xy_new[1]] == 0:     # 坐标有效且没有被访问过
            shortest_path = dfs(xy_new, res+[xy_new])       # 调用下一个节点，第二个参数传递路径
            if shortest_path:                               # 只有dfs返回不为空时，才能返回，空时不能返回，程序会提前结束
                return shortest_path                

#---------------------------------------------------------------------------------
shortest_path = dfs(xy0, res)
if shortest_path:
     for i in shortest_path:
        print('('+str(i[0])+','+str(i[1])+')')
else:
    print('none')
#---------------------------------------------------------------------------------