BFS加visited记录路径（注意前进顺序是下左右上）

解题思路:

bfs找路径 不同的是路过一个点，不是像往常那样，把visited[x][y]记为1，而是记下怎么到的这个点，如1，2前进到1，3 。那么是往右一个单位，记下R，从而记录路径
]注意事项:
这题很坑的是 有时候最短路径有很多可能，但是官方答案只认其中一种，官方答案要求的前进顺序是 下左右上。。。这里卡了好久
参考代码:

def bfs(mazelst,row,col):
    visited=[[0 for i in range(col)] for j in range(row)]
    #print(visited)
    #slst=getS(mazelst,row,col)
    visited[0][0]=1
    mq=[]
    mq.append([0,0])
    chg=[[1,0],[0,-1],[0,1],[-1,0]]
    chgw=['D','L','R','U']
    length=0
    row=len(mazelst)
    col=len(mazelst[0])
    while mq:        
        tmp=[]
        length+=1
        while mq:
            a=mq.pop(0)
            #judge in maze
            for i in range(len(chg)):
                nr=a[0]+chg[i][0]
                nc=a[1]+chg[i][1]
                if nr==row-1 and nc==col-1:
                    visited[nr][nc]=chgw[i]
                    #print(visited)
                    a=""
                    while not(nr==0 and nc==0):
                        a+=visited[nr][nc]
                        #print(visited[nr][nc])
                        t=chgw.index(visited[nr][nc])
                        nr=nr-chg[t][0]
                        nc=nc-chg[t][1]
                    #a+=visited[nr][nc]
                    print(length)
                    print(a[::-1])
                        
                    return length
                else:
                    if nr>=0 and nr<row and nc>=0 and nc<col:
                        if mazelst[nr][nc]==0 and visited[nr][nc]==0:                        
                            tmp.append([nr,nc])
                            visited[nr][nc]=chgw[i]

        mq=tmp.copy()
    return -1
                    


randc=list(map(int,input().split()))
mazelst=[]
for i in range(randc[0]):
    
    nowR=list(map(int,input()))
    mazelst.append(nowR)
a=bfs(mazelst,randc[0],randc[1])