試題 算法提高 學(xué)霸的迷宮（bfs）
問(wèn)題描述
學(xué)霸搶走了大家的作業(yè)宇智，班長(zhǎng)為了幫同學(xué)們找回作業(yè)蔓搞，決定去找學(xué)霸決斗。但學(xué)霸為了不要?jiǎng)e人打擾随橘，住在一個(gè)城堡里喂分，城堡外面是一個(gè)二維的格子迷宮，要進(jìn)城堡必須得先通過(guò)迷宮机蔗。因?yàn)榘嚅L(zhǎng)還有妹子要陪蒲祈，磨刀不誤砍柴功，他為了節(jié)約時(shí)間萝嘁，從線人那里搞到了迷宮的地圖梆掸，準(zhǔn)備提前計(jì)算最短的路線⊙姥裕可是他現(xiàn)在正向妹子解釋這件事情酸钦，于是就委托你幫他找一條最短的路線。
輸入格式
第一行兩個(gè)整數(shù)n咱枉， m卑硫，為迷宮的長(zhǎng)寬。
接下來(lái)n行庞钢，每行m個(gè)數(shù)拔恰，數(shù)之間沒(méi)有間隔，為0或1中的一個(gè)基括。0表示這個(gè)格子可以通過(guò)颜懊，1表示不可以。假設(shè)你現(xiàn)在已經(jīng)在迷宮坐標(biāo)(1,1)的地方，即左上角河爹，迷宮的出口在(n,m)匠璧。每次移動(dòng)時(shí)只能向上下左右4個(gè)方向移動(dòng)到另外一個(gè)可以通過(guò)的格子里，每次移動(dòng)算一步咸这。數(shù)據(jù)保證(1,1)夷恍，(n,m)可以通過(guò)。
輸出格式
第一行一個(gè)數(shù)為需要的最少步數(shù)K媳维。
第二行K個(gè)字符酿雪，每個(gè)字符∈{U,D,L,R},分別表示上下左右。如果有多條長(zhǎng)度相同的最短路徑侄刽，選擇在此表示方法下字典序最小的一個(gè)指黎。
樣例輸入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
樣例輸出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
思路：
從題意中可以看出此題是迷宮題只不過(guò)要算出如何走的位置和最短路相同時(shí)選擇在此表示方法下字典序最小的一個(gè)。
我們可以知道迷宮題是個(gè)經(jīng)典的bfs廣域思想題州丹，他的思想就是把開(kāi)頭隊(duì)列存到隊(duì)列中醋安，然在用一個(gè)列表存儲(chǔ)我走過(guò)的值，并記錄走的對(duì)應(yīng)軌跡墓毒。
我們第一步先建立一個(gè)函數(shù)bfs吓揪，然后在里面建存隊(duì)列的列表。
我用的是d 然后在存一個(gè)開(kāi)頭我們知道起點(diǎn)是（1所计，1）柠辞，但我從（0，0）開(kāi)始的個(gè)人習(xí)慣把醉箕。我們?cè)谟靡粋€(gè)字典鍵來(lái)存走過(guò)的路钾腺，值來(lái)存對(duì)應(yīng)的軌跡。然后我們需要按順序的從DLRU開(kāi)始走一步讥裤。因?yàn)轭}目說(shuō)了最短路相同時(shí)選擇在此表示方法下字典序最小的一個(gè)，然后我們把走到下步的值用x1,y1存儲(chǔ)起來(lái)姻报， 然后我們就開(kāi)始判斷條件己英，我們首先不可以走走過(guò)的路，下面就是當(dāng)p[x1,y1]p字典有這個(gè)鍵時(shí)我們就不管吴旋。
try:
p[x1,y1]
except:
當(dāng)沒(méi)有時(shí)我們就判斷x1和y1是否超出界限"-1<x1<n and -1<y1<m " 然后在判斷是否是可以走的路mp[x1][y1]=="0"损肛。
當(dāng)上面條件都滿足時(shí)我們就把對(duì)應(yīng)點(diǎn)放入隊(duì)列中然后存儲(chǔ)到該點(diǎn)的軌跡，上個(gè)點(diǎn)的軌跡加現(xiàn)在是從那邊過(guò)來(lái)的反向就是本點(diǎn)的軌跡p[x1,y1]=p[x,y]+s[i]荣瑟。當(dāng)該點(diǎn)到終點(diǎn)時(shí)我們就算出終點(diǎn)走的軌跡治拿。
程序：
n,m=map(int,input().split())
mp=[list(input()) for i in range(n)] #存入圖
s="DLRU"
f=[[1,0],[0,-1],[0,1],[-1,0]] #各個(gè)方向標(biāo)記
def bfs():
p={} #存儲(chǔ)軌跡及 位置
d=[[0,0]] #隊(duì)列存儲(chǔ)
p[0,0]="" #存儲(chǔ)第一個(gè)點(diǎn)的位置及 軌跡
while d!=[]:
x,y=d.pop(0) #取出隊(duì)列的第一個(gè)點(diǎn)
for i in range(4):
x1=f[i][0]+x #下個(gè)點(diǎn)的位置
y1=f[i][1]+y
try:
p[x1,y1] #判斷是否有當(dāng)前這個(gè)點(diǎn)
except:
if -1<x1<n and -1<y1<m and mp[x1][y1]=="0" : #判斷是否超界限是否路可以走
d.append([x1,y1]) #存入列表中
p[x1,y1]=p[x,y]+s[i] #記錄該點(diǎn)的軌跡
if x1==n-1 and m-1==y1: #是否到達(dá)終點(diǎn)
return p[x1,y1]
c=bfs()
print(len(c))
print(c)
禁止轉(zhuǎn)載。僅用于自己學(xué)習(xí)笆焰。對(duì)程序錯(cuò)誤不負(fù)責(zé)劫谅。
