題目： 輸入一個二維數(shù)組，1表示不可走，0表示可走，通路是從左上角往右下角找，右下角是出口。要求找到路徑最短的走法，且優(yōu)先級為下左上右，若發(fā)現(xiàn)步數(shù)一致的走法，則按照字典序?qū)Σ綌?shù)結(jié)果進行排序。
該迷宮為：
0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1
0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 1
1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0
0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1
1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1
1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0
1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 1
0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1
1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1
1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1
1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
1 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0
0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1
1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0
我們使用的方法是BFS也就是廣度優(yōu)先搜索。廣度優(yōu)先搜索需要利用隊列來解決問題，其思想就是，從某點開始，探索一系列可以走的點，然后再繼續(xù)從這些點開始，找到更多能走的點，最后達到我們所要完成的目標，點的不重復(fù)問題，以及先后順序問題是非常值得注意的，本題的思想就是從入口出發(fā)，然后依次通過BFS找到可以走的點，然后將他們存放到隊列中，依次走，去掉重復(fù)點，然后通過不斷的循環(huán)，可以找到最快的路徑，也可以利用特定的排序來決定他的走步的先后順序，非常巧妙，此題應(yīng)該還有多解，以后更新。實現(xiàn)算法明天手打。
#程序來自CSDN的一個大佬，我只是學(xué)習(xí)之后自己默寫了一遍
#來保存小孩在迷宮中的位置，包含三個元素，一個是橫坐標，一個是縱坐標，一個是已經(jīng)走過的步數(shù)以及路線
class Node(object):
def __init__(self,x,y,w):
self.x = x
self.y = y
self.w = w
def __str__(self):
return self.w
def up(node):
return Node(node.x-1,node.y,node.w+'U')
def down(node):
return Node(node.x+1,node.y,node.w+'D')
def left(node):
return Node(node.x,node.y-1,node.w+'L')
def right(node):
return Node(node.x,node.y+1,node.w+'R')
#這句if的意思是指只在本文件運行時才會進行執(zhí)行，__name__在本文件直接執(zhí)行時，他的值為文件的名稱包含后綴，
#而當本文件以import的方式進行引用時，__name__的值為文件的名稱不包含后綴，而__main__始終指向文件的名稱
#包含后綴。所以達到了直接運行時執(zhí)行以下的內(nèi)容，但是作為包import到其他項目中去，if判斷為False，所以不
#執(zhí)行
if __name__ == "__main__":
#第一步，初步準備
m,n = map(int,input().split()) #map是python中的內(nèi)置函數(shù)，map(function,iterable),對于每個數(shù)據(jù)都執(zhí)行function，返回一個迭代器
visited = set() #建立一個集合，來存儲已經(jīng)走過的位置，建立集合是因為集合具有不可重復(fù)性，在BFS中，有可能發(fā)生探索過程中往回走的情況，要通過這種方式進行杜絕
queue = [] #建立一個隊列，建立隊列是因為要進行廣度探索，所以要記住每一次走過的點，以及下一次要走的點，這個隊列可以對走點的先后順序進行保證，同時保證廣度搜索不會丟點
#第二步，輸入數(shù)據(jù)
map_int = [[0]*(n+1)]#因為迷宮是要從1,1為起點的，所以要在上方建立一排0，和左邊建立一排0，這樣開始的點就可以為1,1了
#map_int的格式問題：因為我們要做的是二維迷宮，所以我們選擇使用二維數(shù)組，每一行是一個數(shù)組，因為在python中input的類型是str，所以要編入數(shù)組還需要進行類型轉(zhuǎn)換
for i in range(1,m+1):
map_int.append([0]*(n+1))#加入一行元素，個數(shù)與迷宮一行數(shù)字的個數(shù)相同，達到占位的效果
nums = input()#輸入迷宮數(shù)據(jù)，按照行輸入，不必有空格
nums = '0' + nums#如之前所說，迷宮要從1,1,開始走，所以左方也要加一排0站位
for j in range(0,n+1):
map_int[i][j] = ord(nums[j]) - 48 #ord為python中的內(nèi)置函數(shù)以一個字符為對象，返回他的ASCII碼值，本程序使用這種方法將str轉(zhuǎn)換為字符串
node = Node(1,1,"") #創(chuàng)建第一個節(jié)點
queue.append(node) #將節(jié)點放入到隊列之中
#第三步，進行正式的迷宮廣度搜索
while len(queue) != 0:
movenode = queue[0] #將隊列中第一個節(jié)點開始移動
queue.pop(0) #降低一個節(jié)點移出隊列
movestr = str(movenode.x)+" "+str(movenode.y)#將節(jié)點所移動到的位置記錄下來，以防止隊列將走過相同的節(jié)點
if movestr not in visited:
visited.add(movestr) #將節(jié)點加入到集合中，然后通過結(jié)合來對是否以后節(jié)點進行判斷，如果已經(jīng)存在在集合中，則不再加入隊列
#如果滿足條件，則對節(jié)點進行廣度搜索，找到他能走到的符合規(guī)則的下一個點
if movenode.x ==m and movenode.y ==n:#判斷是否已經(jīng)走到了終點，若走到終點，因為我們只是找最短路徑，第一個到終點的一定是步數(shù)最少的，所以我們可以直接break
print(movenode.w)
break
#因為題目中要求，同樣步數(shù)時，按照字典序進行優(yōu)先級劃分，所以我們在進行廣度探索時，也按照字典序作為優(yōu)先級進行遍歷，即為D>L>R>U
if movenode.x<m:#向下
if map_int[movenode.x+1][movenode.y] ==0:
queue.append(down(movenode))
if movenode.y>1:#向左
if map_int[movenode.x][movenode.y-1] ==0:
queue.append(left(movenode))
if movenode.y<n:#向右
if map_int[movenode.x][movenode.y+1] ==0:
queue.append(right(movenode))
if movenode.x>1:#向上
if map_int[movenode.x-1][movenode.y] ==0:
queue.append(up(movenode))
