題目連結:
題目大意:
輸入第一列給定兩正整數 N 、 M (1 ≦ N 、 M ≦ 10),代表有一個 N 列 M 行之網格區域(左上角座標為 (1, 1) 、 右下角為 (N, M))。接著有 N 列輸入,每列給定 M 個字元,且只會是「.」(可以通行的道路)或是「#」(不能通行的障礙),代表網格區域的地圖。
試問從區域左上角走到右下角最少需要幾步?如果無法抵達,則輸出「-1」。
範例輸入:
3 5
.#...
.#.#.
...#.
範例輸出:
10
解題思維:
用廣度優先搜尋(Breadth First Search,BFS)之精神從起點(左上角)擴張到終點(右下角),如
這題和
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。