題目連結:
題目大意:
輸入第一列給定一正整數 N (N ≦ 100),代表有一個 N × N 個迷宮,其只由「#」(障礙物)以及「.」(路)組成。接著有 N 列輸入,每列給定 N 個字元,代表迷宮的構成。
你固定從 (2, 2) (即迷宮的第二列第二行的位置(索引值從 1 開始算))開始走,試問最短需要幾步(起點本身也算一步)才能走到 (N - 1, N - 1)。每一步只能走在「.」(路)上,且每次只能往上下左右相鄰之格子前進。如果不可能抵達終點,則輸出「No solution!」。
範例輸入:
9
#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
(為了排版,所以使用了不同的字型)
範例輸出:
13
解題思維:
典型的迷宮題,即套用了廣度優先搜尋(Breadth First Search,BFS)的精神,參見
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。