递归算法--02 迷宫问题：指定单入口和单出口，找到所有路径即可

相似问题解决请参看：递归算法--01 迷宫问题：指定单入口和单出口，找到任意路径即可_江南野栀子的博客-CSDN博客

1. 迷宫问题描述

        问题背景：

        给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙体（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。

        求解目标：

        你的目标是找到通往指定出口的所有路径。出口是 maze 边界 上的 空格子，由用户指定。如果找不到，则返回空。
 

2. 迷宫问题代码实现

import copy

# 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），
# 矩阵中有空格子（用 '.' 表示）和墙体（用 '+' 表示）。
test_maze=[["+",".","+",".",".","+",".",".","+",".",".",".","+","+",".",".",".",".","+","."],\
          [".","+","+",".","+",".",".",".","+","+","+",".","+",".",".","+",".","+","+","."],\
          ["+",".",".",".",".","+",".",".",".",".",".",".",".",".","+",".",".","+","+","."],\
          [".",".",".","+","+",".",".",".","+",".","+",".",".","+",".",".","+",".",".","."],\
          ["+",".",".",".",".",".","+",".",".","+",".",".","+","+",".","+","+",".",".","."],\
          [".","+",".",".",".",".","+",".","+",".",".",".",".",".",".","+",".","+","+","+"],\
          [".",".",".","+",".",".","+",".","+","+",".","+",".",".",".",".",".","+",".","."],\
          [".",".",".",".",".","+","+","+",".",".",".","+",".","+","+","+","+",".",".","."],\
          [".",".","+",".",".","+",".","+",".",".","+",".",".",".",".",".",".",".","+","."],\
          [".",".",".",".",".",".","+",".","+",".",".",".","+",".","+",".",".",".","+","."],\
          [".","+",".","+",".",".","+",".","+",".",".","+",".","+",".",".",".",".",".","+"],\
          [".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".",".","."],\
          ["+","+","+","+",".",".","+",".",".",".","+",".",".","+","+","+",".",".",".","."],\
          [".",".","+","+",".","+",".",".",".",".",".","+","+",".",".","+",".",".",".","."],\
          [".",".",".","+",".",".",".",".",".",".",".","+",".",".",".",".","+",".",".","."],\
          [".","+","+",".",".","+",".",".",".",".","+","+",".","+","+",".",".",".","+","."],\
          ["+",".",".",".",".",".","+",".",".",".",".","+",".",".",".",".",".",".",".","."],\
          [".",".",".",".","+",".",".",".","+",".",".","+",".",".",".",".",".",".",".","."]]

# m,n 分别是迷宫的行数、列数
m,n=len(test_maze),len(test_maze[0])

# 上下左右四个方向的偏移值
moves=[[-1,0],[1,0],[0,-1],[0,1]]

# 判断 pos 所在位置是否可以同行
# 同行的标准是在迷宫内，且不触及墙体
def passable(maze,pos):
    if( -1<pos[0]<m and -1<pos[1]<n  and maze[pos[0]][pos[1]]=="."):
        return(True)
    else:
        return(False)

def remark(maze,pos):
    maze[pos[0]][pos[1]]="d"


# 在 start、end 之间找到所有的通畅路径
def find_all_passable_paths(maze,pos,end):
    path=[]
    # remark 是为了标记此处已经到达，避免反复到同一个地方，形成死循环
    remark(maze,pos)
    
    # 如果已经到达出口处
    if(pos==end):
        # 请注意，此处要将通畅的地点再取消标记，否则不能得到所有路径
        maze[pos[0]][pos[1]]="."
        path.append([pos])
        return(path)
    
    find=False
    # 下一个地址是依据上下左右的顺序，依次去判断下一个地址能否到出口
    for i in range(len(moves)):
        next_pos=[pos[0]+moves[i][0],pos[1]+moves[i][1]]
        
        # 如果下一个地址是通畅的，既没有被标记，也没有触及墙体
        if(passable(maze,next_pos)):
            
            # 获得下一个地址到出口的路径
            extend_path=find_all_passable_paths(maze,next_pos,end)
            
            # 如果得到的路径不为空，表示可以抵达出口
            if(extend_path is not None) :
                find=True
                for tmp in extend_path:
                    path.append([pos]+tmp)
                
            
            # 请注意，不会在此处之间 return 返回，因为希望获得所有的路径
                
    if(find):
        # 请注意，此处要将通畅的地点再取消标记，否则不能得到所有路径
        maze[pos[0]][pos[1]]="."
        return(path)
    else:
    # 这个很重要，当递归找不到出口时候，返回的 path 是空列表
        return(None)

3. 测试代码以及结果

3.1 测试代码实现

# 这个函数是为了测试用的，它会将搜索的路径用标号显示出来，
# 从而大家可以一目了然是否正确
def show_path(maze,path):
    count=0
    # 为了不影响原来的迷宫，深拷贝一个一模一样的迷宫，在此的基础上显示路径
    show_maze=copy.deepcopy(maze)
    for pos in path:
        # 这是一行测试代码，在展示路径时候，顺便检查一下路径是否正确
        # 如果路径上的位置原来就不通畅，那么则提示出来
        if(not passable(show_maze,pos)):
            print("Something is Wrong with {0}".format(pos))
        else:
            count+=1
            show_maze[pos[0]][pos[1]]=str(count)
    i=0
    for row in show_maze:
        print("{0} ==>".format(i),end=" ")
        for tmp in row:
            print(tmp.center(4),end=" ")
        print()
        i+=1

# 显示初始的迷宫状态
print("--------------------------------------Show Original Maze--------------------------------------".center(100))
copied_maze=copy.deepcopy(test_maze)
show_path(copied_maze,[])

# 下面是测试代码
#为了做多次测试，不想影响原来的迷宫，所以进行深拷贝 
def test_code_allpaths(start,end):
    global test_maze
    copied_maze=copy.deepcopy(test_maze)


    paths=find_all_passable_paths(copied_maze,start,end)
    if(paths is not None):
        print("-------------------------------------------  Found Path  ------------------------------------------".center(100))
        # 假设有多条路径
        i=1
        for path in paths:
            print(path)
            if(paths.count(path)>1):
                print("Something is wrong!")
                break
            print(i)
            print("-------------------------------------------  To Show Path  {0}------------------------------------------".format(i).center(100))
            show_path(test_maze,path)
            i+=1
    else:
        print("------------------------------------------- Not found path------------------------------------------".center(100))

先看看初始的迷宫状态

3.2 测试用例结果

        因为要返回多条路径，所以返回结果非常庞大，此处只给两个测试用例结果，有兴趣的同学可以自行调用测试代码验证。

3.2.1 用例 1 以及结果

print("*"*55+" Test Case 1 "+"*"*55)
start=[11,0]
end=[17, 17]
test_code_allpaths(start,end)

运行结果请自己验证。

3.2.2 用例 2 以及结果

print("*"*55+" Test Case 6 "+"*"*55)
start=[11,0]
end=[7, 0]
test_code_allpaths(start,end)