真正python 迷宫最短路径解法（华为机试）

为何是真正？因为看了下别人的python 解法，都有个弊端，就是只能做从起点0到终点的唯一路径的题，如果出现分支，或者多路径求最短那么那些方法就不适用了。相对而言，以下做法不仅可以实现多路径下的最短到终点探索，还能实现任意两点之间的最短路径返回，而且代码还不长，符合python人生苦短特点，所以成为真！到最后面附原试题：
python是解简单题最好用的方法

#利用动态规划和递归解
def jud(x,y,l,ll,lll):#求x,y点坐标在迷宫里的可能走法，即向上，向下，向左，向右
    n,m=len(l)-1,len(l[0])-1 #l为迷宫位置二维图，ll为迷宫的每点从起点到该点
    k=[]     #的最短路径，lll为记录正在探索的从起点到该点的路线用以避免走重复
    if x+1<=n and (x+1,y) not in lll and l[x+1][y]!=1:k+=[(x+1,y)]  
    if x-1>=0 and (x-1,y) not in lll and l[x-1][y]!=1:k+=[(x-1,y)]
    if y+1<=m and (x,y+1) not in lll and l[x][y+1]!=1:k+=[(x,y+1)]
    if y-1>=0 and (x,y-1) not in lll and l[x][y]!=1:k+=[(x,y-1)]
    return k
def mg(x,y,l,ll,lll):#x,y为该点坐标，其余同上，探索x,y的走法
    k=jud(x,y,l,ll,lll)#k为可能的走法
    lll+=[(x,y)]        #lll位置储存
    if len(k)>0:        #是否为可走
        for v in k:
            x1,y1=v      
            if not ll[x1][y1] :  #如果x1,y1位置 还没有路径信息，用x,y位置进
                ll[x1][y1]=ll[x][y]+[(x1,y1)] #行更新          
            if len(ll[x1][y1])>=len(ll[x][y])+1: #如果x1,y1之前储存的路径#要长于从x,y的路径到x1,y1的，则更新x1,y1路径信息
                ll[x1][y1]=ll[x][y]+[(x1,y1)]
            mg(x1,y1,l,ll,lll.copy())  #再对x1,y1 这点进行探索
    return False

while True:
    try:
        nn,mm=list(map(int,input().split())) 
        l,ll,lll=[],[],[]
        for i in range(nn):
            l+=[list(map(int,input().split()))]
        for i in range(nn):
            ll.append([])
            for j in range(mm):
                ll[i].append([])
        ll[0][0]=[(0,0)] 
        mg(0,0,l,ll,lll)   # 设置起始点为（0，0），你也可以设为其他点为起始，
        for v in ll[-1][-1]: #来探索其他点到任意一点的最短位置              
            print("(%d,%d)"%(v[0],v[1])) #ll[-1][-1], 指的是将右下角一点设
    except:
        break
#为终点并打印出来，你也可以求其他点，如ll[2][3],来实现任意
                                          #两点求最短路

题目描述
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {

    0, 1, 0, 0, 0,


    0, 1, 0, 1, 0,


    0, 0, 0, 0, 0,


    0, 1, 1, 1, 0,


    0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。

Input

一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

输入描述:
输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径，格式如样例所示。

示例1
输入
复制
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出
复制
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)斜体内容