a634. 14. Knights Path
Tags :
Accepted rate : 85人/94人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-15 08:31

Content

在西洋棋中,騎士的走法獨特而有趣。它只能沿著一個「L」形路徑走,先垂直或水平走兩格,然後再向左或向右走一格。右圖顯示一個標準的 8×8 棋盤,有一個騎士在 c6 這一格。從這個位置,騎士可以走到以圓圈標示的八個位置。

你的工作是要找出騎士從棋盤上的一個位置走到另一個位置的最短路徑。與真正下棋時不同的是,你不可以落在有其他棋子的地方 (我們稱之為「路障」)。注意,騎士依上述方式移動每一步時,它可以「跨過」其他的棋子,但是必須茖在空的格子上。

Input

每筆測資的第一行含有起始和結束的位置,以空白隔開。棋盤的左上角為 a8,右下角為 h1。所有的字母均為小寫。

接下來有一個或多個「路障」位置,最後一個路障之後會有一個「xx」作為結束。最多會有 31 個路障,所有的輸入都是正確的。

Output
你的程式要輸出從起始位置到目的位罝的最短路徑中的每一步。你也要述明所需的總步數。如果有多條最短路徑,請依字典順序輸出所有的路徑。
Sample Input #1
c6 c5
b3
a6
b7
d7
xx
Sample Output #1
The shortest solution is 3 move(s).
Solution: c6 b4 d3 c5
Solution: c6 d4 e6 c5
Solution: c6 d8 e6 c5
Solution: c6 e5 d3 c5

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
//經查,本題原測資有誤,已更正并重測 by liouzhou_101 2013-02-22 14:15
Tags:
出處:
HP CodeWars2007 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」