Submit Ranklist
Problem : 172 - 拯救國王
Problem Statistics
Solved Member:
20 Submission:
102 User Tried:
24 Statement:
自從上次亞瑟王和他的好騎士們有過聚會之後，這次亞瑟王快樂的去森林裡打獵
所謂天有不測風雲、人有旦夕禍福、人之將死其言也善…(中略)，亞瑟王身中劇毒，不但無法行動、不趕快治療的話還會死掉。
亞瑟王打手機呼叫了他最信任的一位騎士來森林裡救他，騎士會從一個給定的起點出發，他必須先踩到有藥草的格子摘了藥草以後，再盡速移動到國王所在的格子來治好國王。
B B . .
. . B X
A C . .
上面是一種森林的地形圖
「.」代表一般的地點
「X」代表不可到達的障礙物
「A」表示騎士的出發點
「B」是散布在森林各地的藥草
「C」表示國王所在位置
騎士的移動方法和西洋棋中的騎士一樣，是走日字型的，如下表所示
騎士所在位置是A，他可以選擇移動到這8個標示G的位置，只要目的地沒障礙物而且沒超出地圖邊界的話
請問：騎士最少總共要走幾步才能採到藥草並且拿給國王？
Input:Output:
每個測試檔僅有一筆測試資料。
第一行有兩個正整數n,m，以空格隔開，表示森林地圖的長寬
緊接著n行，每行有m個字元，表達了各地的地形(意義請見前述)
其中n,m不超過1000
我們保證地圖是合法的，每張地圖有且僅有一個A和一個C，和至少一個B
輸出唯一的一行，包含一個整數，表示最少要走幾步才能達成目標
如果無論如何也無法達成，請輸出-1
Sample Input:Sample Output:
Sample 1
3 4
BB..
..BX
AC..
Sample 2
1 3
ABC
Sample 1
3
Sample 2
-1
HINT:
所謂天有不測風雲、人有旦夕禍福、人之將死其言也善，亞瑟王正準備拉弓瞄準一頭豬。
(一個被我派去殺野豬的農民, 反而被野豬殺了！)
當他放開手的時候，愕然發現飛出去的不是箭矢，他把整把弓給彈出去了！！！
亞瑟王探索附近的區域找他那把飛出去的弓，於是他見到了一座美麗的大湖，湖中冒出了女神：
「你掉的是我左手拿的這把伐木工、還是我右手拿的這把建築工呢？」
世風日下，道德淪亡；邪說紛紛，人慾橫流
平常亞瑟王都宅在皇宮打世紀帝國，也難怪杜甫老先生寫下「朱門酒肉臭，路有凍死骨；榮枯咫尺異，惆悵難再述」
總之亞瑟王聽到了關鍵字，不由分說興奮的大喊：「糧糧糧糧糧糧糧糧草徵收人！！！」
女神答：「你很誠實(狀況外吧這傢伙)，我決定把伐木工、建築工還有糧草徵收人都送給你」
殊不知這三位村民已經沉在湖底多年，早就變成了沒有意識的殭屍
失去唯一防身武器的亞瑟王和殭屍纏鬥許久，終於逃脫這些村民的魔爪
不過這時，亞瑟王身中劇毒，不但無法行動、不趕快治療的話還會死掉。
Source:
101附中校內賽
Problem Setter
lajisongyy_jack1 Testdata:
| Test | Time | Memory | Score |
|---|
| 0-1 | 2000ms | 65536kb | |
| 0-2 | 2000ms | 65536kb | |
| 1 | 2000ms | 65536kb | 20 |
| 2 | 2000ms | 65536kb | 20 |
| 3 | 2000ms | 65536kb | 20 |
| 4 | 2000ms | 65536kb | 20 |
| 5 | 2000ms | 65536kb | 20 |