a122. 小哞的台大迷宮 - 彰化精誠中學

內容

台大教授非常欣賞小哞的大頭，決定錄取小哞。不料，報到的第一天小哞便迷了路，眼前一切彷彿一片迷宮。已知小哞、電機大樓的位置和迷宮的樣貌(0代表可走的路，其他符號代表障礙物)，每次移動可走上下左右的0。請設計一隻程式，幫不愛走路的小哞算出到達電機大樓的最短距離。

BFS筆記:

寬度優先搜索，從某個狀態出發探索所有可以到達的狀態。與DFS不同之處在於搜索的順序，BFS總是先搜索距離初始狀態近的狀態。也就是說，他是按照初始狀態->只需一次轉移一次即可到達的狀態->只需兩次轉移一次即可到達的狀態->......。對於同一狀態，BFS只經過一次，因此複雜度為O(狀態數*轉移方式)。

輸入說明

第一列輸入迷宮大小N,M(N,M<=100)

第二列輸入小哞位置座標

第三列輸入電機大樓位置座標

接著輸入N列M行的迷宮

輸出說明

輸出最短路徑的距離

若到達不了電機大樓則輸出can't find

範例輸入 #1

10 10
0 1
9 8
#0#$#$##0#
000000#00#
0#0$#0##0#
0$00000000
#+0$#0#$$#
0000#0000#
0#~#=#=#0#
0000#00000
0~###0###0
0000#0000#

範例輸出 #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

BFS可利用隊列queue實現

標籤:

BFS

出處:

[管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」