Embedded Files
上傳作業：http://203.68.236.9/problem/b0036
內容 ：
彼得王住在 A 王國，他的女兒住在 B 王國。國王從信中得知他女兒生了小孩，他很想看到他的孫子！但這可不是件容易的事。
A 王國和 B 王國之間隔著一座森林，森林中有很多敵人，國王並不想見到他們。如果他們在國王往 B 王國的路上攻擊他，這致命的後果會讓他永遠見不到他的孫子和女兒。
國王的安全議會收集到了敵人位置的情報，這讓事情容易些。由於某未知因素這森林是一個 M x N 的棋盤。(M 代表幾列，N 代表幾行。) N, M <= 100 且為正整數。
國王的敵人如下圖般騎馬。通常馬兒會以西洋棋的方式走 (或跳)。不幸的是國王不能從 A 搭飛機到 B，因飛機還沒發明，因此他以西洋棋的國王的相同方式移動 (細節請參考下圖)。
如果方格 X 有敵人的馬在那兒，國王就不能移到那格。國王走的時候，馬並不移動，但是如果有任一匹馬可以一步走到方格 X，國王就不能移到那格 (除非那格是 A 王國或 B 王國)。
你是 A 王國的電子情報局長 (順帶一提，電腦那時已經發明了)。由於國王等不及了，你必須儘快找出從王國 A 到王國 B 的最短路徑 L。
輸入說明 ：
輸入的第一行含有測試資料的組數 T <= 100。每組測資的第一行含有兩個整數 M 和 N。接下來的 M 行每行含有 N 個屬於集合 S = {'.', 'Z', 'A', 'B'} 的符號。'.' 代表那格是空的，'Z' 代表那格有匹馬，'A' 代表 A 王國，'B' 代表 B 王國。每組測資都恰有一個 A 及 一個 B。
輸出說明 ：
找出每組測試的 L，如果國王到得了 B 王國，印出 "Minimal possible length of a trip is L"，以相對應的數字取代 L。如果國王無法安全抵達 B 王國，印出 "King Peter, you can't go now!"。
範例輸入 ：
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.
範例輸出 ：
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
提示 ：
出處 ：
UVa ACM 11352 (管理：snail)
解題策略
BFS
Page updated
Google Sites
Report abuse