Submit　　Ranklist

Problem : 208 - 拯救國王前傳

Problem Statistics

Solved Member: 7　　Submission: 46　　User Tried: 7

Statement:

在你上次AC了拯救國王(點我進HOJ172)以後

這題是和那題敘述第一行他們的聚會有關

亞瑟王的宮殿相當的大，好比下面這個8*8的西洋棋盤

棋盤上會有恰好一個國王(也就是亞瑟王)，還有若干個騎士
保證不會有兩個騎士一開始在同一個位置

亞瑟王的移動方法是能朝八方位跨一格，如下圖(當然，不可以走出棋盤外)：

亞瑟王的騎士們則是像西洋棋的騎士一樣，走日字型(不可以走出棋盤外)：

同一個格子同時有兩個或以上旗子是沒問題的(2013.1.1補上)

現在，亞瑟王和他的好騎士們想要找個格子來場興奮的聚會

亞瑟王和騎士們行走步數的總和最少是多少呢？

對了，當亞瑟王和騎士走到同一格的時候

懶惰的他會請騎士載他一程、這兩個棋子從此一起行動，只算騎士的步數

Input:Output:

每個測試檔僅一筆測資
第一行有兩個正整數R,C(不超過30和26)，代表此棋盤有R列(Row)、C行(Column)
第二行表達了國王的位置(棋子的位置用一個大寫A~Z字母和一個數字[1,R]來表示)
第三行開始一直到檔案EOF表達了所有騎士的位置，可能沒有騎士、也可能整個棋盤都塞滿了騎士

輸出唯一的一行，選擇了最優的集合地點(以及最優的搭便車方法)時，國王和騎士們的總步數

Sample Input:Sample Output:

8 8
D 4
A 3 A 8
H 1 H 8

HINT:

範例測資集合點為B5
A3騎士：B5
A8騎士：C7-B5
H8騎士：F7-D6-B5
H1騎士：G3-F5-D4(國王上馬)-B5
總共1+2+3+4=10步

--

另外，IOI和USACO原題都沒說明萬一騎士卡死怎麼辦、例如這樣：
2 2
A 1
A 1 A 2 B 1 B 2

不過請大家放心本題沒有這麼白爛的測資

--

題目參考USACO Training 3.3.5 - camelot

測試資料用的是USACO Training的加強版(詳情見NOCOW題解有討論)

NOCOW連結

Source:

IOI 1998

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	5
2	1000ms	65536kb	5
3	1000ms	65536kb	5
4	1000ms	65536kb	5
5	1000ms	65536kb	5
6	1000ms	65536kb	5
7	1000ms	65536kb	5
8	1000ms	65536kb	5
9	1000ms	65536kb	5
10	1000ms	65536kb	5
11	1000ms	65536kb	5
12	1000ms	65536kb	5
13	1000ms	65536kb	5
14	1000ms	65536kb	5
15	1000ms	65536kb	5
16	1000ms	65536kb	5
17	1000ms	65536kb	5
18	1000ms	65536kb	5
19	1000ms	65536kb	5
20	1000ms	65536kb	5