切換
舊版
前往
大廳
主題

ZeroJudge - c117: 00439 - Knight Moves 解題心得

Not In My Back Yard | 2020-09-02 00:00:20 | 巴幣 0 | 人氣 175

題目連結:


題目大意:
輸入有多列,每列給定兩個西洋棋的座標。每個座標由一個小寫英文字母(只會是 a ~ h)以及一個數字(只會是 1 ~ 8)組成,前者代表行數、後者為列數。

試問如果使用騎士(Knight)從第一個座標出發,最少多少步可以抵達第二個座標?

注:騎士的走法類似於象棋中的馬。參見維基圖示。



範例輸入:
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6


範例輸出:
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.


解題思維:
其實跟這題相當地類似。就是從起點開始,利用廣度優先搜尋(Breadth First Search,BFS)的精神,一步一步地擴散並將被擴散到的位置加入佇列裡後面再從該位置繼續擴散。重複擴散到的位置不需要加進去。

而本題騎士的「擴散」方式不是直接上下左右或是九宮格的擴散而是有自己的走法(見題目大意)。




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

創作回應

更多創作