前往
大廳
主題

ZeroJudge - f671: FJCU_109_Winter_Day1_Lab6 最短路徑 解題心得

Not In My Back Yard | 2021-02-28 00:00:10 | 巴幣 0 | 人氣 296

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M (1 ≦ N 、 M ≦ 10),代表有一個 N 列 M 行之網格區域(左上角座標為 (1, 1) 、 右下角為 (N, M))。接著有 N 列輸入,每列給定 M 個字元,且只會是「.」(可以通行的道路)或是「#」(不能通行的障礙),代表網格區域的地圖。

試問從區域左上角走到右下角最少需要幾步?如果無法抵達,則輸出「-1」。



範例輸入:
3 5
.#...
.#.#.
...#.


範例輸出:
10


解題思維:
用廣度優先搜尋(Breadth First Search,BFS)之精神從起點(左上角)擴張到終點(右下角),如這題這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作