d191: 11352 - Crazy King
Tags :
Accepted rate : 134人/152人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-21 11:33

Content

彼得王住在 A 王國,他的女兒住在 B 王國。國王從信中得知他女兒生了小孩,他很想看到他的孫子!但這可不是件容易的事。 

A 王國和 B 王國之間隔著一座森林,森林中有很多敵人,國王並不想見到他們。如果他們在國王往 B 王國的路上攻擊他,這致命的後果會讓他永遠見不到他的孫子和女兒。

國王的安全議會收集到了敵人位置的情報,這讓事情容易些。由於某未知因素這森林是一個 M x N 的棋盤。(M 代表幾列,N 代表幾行。) N, M <= 100 且為正整數。

國王的敵人如下圖般騎馬。通常馬兒會以西洋棋的方式走 (或跳)。不幸的是國王不能從 A 搭飛機到 B,因飛機還沒發明,因此他以西洋棋的國王的相同方式移動 (細節請參考下圖)。


如果方格 X 有敵人的馬在那兒,國王就不能移到那格。國王走的時候,馬並不移動,但是如果有任一匹馬可以一步走到方格 X,國王就不能移到那格 (除非那格是 A 王國或 B 王國)。 

你是 A 王國的電子情報局長 (順帶一提,電腦那時已經發明了)。由於國王等不及了,你必須儘快找出從王國 A 到王國 B 的最短路徑 L。 

Input
輸入的第一行含有測試資料的組數 T <= 100。每組測資的第一行含有兩個整數 M 和 N。接下來的 M 行每行含有 N 個屬於集合 S = {'.', 'Z', 'A', 'B'} 的符號。'.' 代表那格是空的,'Z' 代表那格有匹馬,'A' 代表 A 王國,'B' 代表 B 王國。每組測資都恰有一個 A 及 一個 B。
Output
找出每組測試的 L,如果國王到得了 B 王國,印出 "Minimal possible length of a trip is L",以相對應的數字取代 L。如果國王無法安全抵達 B 王國,印出 "King Peter, you can't go now!"。
Sample Input
4
5 5
.Z..B
..Z..
Z...Z
.Z...
A....
3 2
ZB
.Z
AZ
6 5
....B
.....
.....
..Z..
.....
A..Z.
3 3
ZZ.
...
AB.
Sample Output
King Peter, you can't go now!
Minimal possible length of a trip is 2
King Peter, you can't go now!
Minimal possible length of a trip is 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa11352 [管理者:
snail (蝸牛)
]


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