python求地圖最短距離算法，大神們求指教

zp307300084

假設(shè)這是一個(gè)地圖，我要計(jì)算出走完這個(gè)地方的為0的最短距離
[
[1,1,1,1,1],
[1,0,0,0,1],
[1,0,0,1,1],
[1,1,0,0,1],
[1,1,1,1,1],
]

比如：'L' = 向左1步；'R' = 向右1步；'U' = 向上1步；'D' = 向下1步

最短距離則為：LLDRDR

這個(gè)沒(méi)有出入口的，人可以隨便放，只要走完全部標(biāo)記為0的地方就行

zp307300084

地圖是標(biāo)準(zhǔn)的2維數(shù)組，5*5、4*4、6*6依次類推 ，中間不會(huì)出現(xiàn)1,0,1,0,1斷開(kāi)的情況，線都是連著的

q1208c

回復(fù) 1# zp307300084


第一, 能不能把你的 代碼 放在 code 里. 這樣, 格式不會(huì)變, 看得更清楚.

第二, 我沒(méi)看懂你的答案, 不管人原來(lái)在哪里, 你的答案都走不出去. 另外, 你沒(méi)說(shuō)是 1 能走還是 0 能走.


第三, 我不一定能解答你的問(wèn)題, 不過(guò), 我對(duì)問(wèn)題的結(jié)果很感興趣.

XINBADA426

至少說(shuō)明入口在哪里，出口在哪里啊。。

太平洋上的我

感覺(jué)這是圖論和拓?fù)鋵W(xué)。。。
點(diǎn)有三種情況，我稱為伯仲叔季，表示分別周圍有4、3、2、1個(gè)1
這樣定義：
伯：到了這個(gè)點(diǎn)后有三種選項(xiàng)，最復(fù)雜的點(diǎn)
   0
0 0 0
   0
仲：到了這個(gè)點(diǎn)后有兩種選擇
   1
0 0 0
   0
叔：到了這個(gè)點(diǎn)后沒(méi)有選擇,只能直走或轉(zhuǎn)彎
   1           0
0 0 0     0 0 1
   1           1
季：起止點(diǎn)，到了這個(gè)點(diǎn)后就結(jié)束或者必須繞路（即成為一個(gè)新的起點(diǎn)）
   1
1 0 1
   0
所以就是，從季點(diǎn)作為起點(diǎn)，開(kāi)始走，碰到仲點(diǎn)就成一個(gè)二叉，碰到伯點(diǎn)就成一個(gè)三叉，遍歷所有可能，當(dāng)長(zhǎng)度超過(guò)最短長(zhǎng)度（right_way_len)時(shí)，就continue，遍歷上一個(gè)叉的另一種可能。直到遍歷完所有可能。

想法是這樣，編的話 得花點(diǎn)心思

icymirror

可以考慮圖算法里面的廣度優(yōu)先搜索，探索得到指定開(kāi)始點(diǎn)和結(jié)束點(diǎn)之間的路徑，那搜索到的就是你找到的路徑。

古龍想的回憶

五元組表示的是什么意思啊