前往
大廳
主題

ZeroJudge - a982: 迷宮問題#1 解題心得

Not In My Back Yard | 2021-03-20 22:46:17 | 巴幣 2 | 人氣 512

題目連結:


題目大意:
輸入第一列給定一正整數 N (N ≦ 100),代表有一個 N × N 個迷宮,其只由「#」(障礙物)以及「.」(路)組成。接著有 N 列輸入,每列給定 N 個字元,代表迷宮的構成。

你固定從 (2, 2) (即迷宮的第二列第二行的位置(索引值從 1 開始算))開始走,試問最短需要幾步(起點本身也算一步)才能走到 (N - 1, N - 1)。每一步只能走在「.」(路)上,且每次只能往上下左右相鄰之格子前進。如果不可能抵達終點,則輸出「No solution!」。



範例輸入:
9
#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########

(為了排版,所以使用了不同的字型)


範例輸出:
13


解題思維:
典型的迷宮題,即套用了廣度優先搜尋(Breadth First Search,BFS)的精神,參見這題




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

創作回應

更多創作