## 2013年8月2日

### UVa 11352 - Crazy King

#include <cstdio>
#include <queue>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;
const int dr[8] = {1, 2, 1, 2, -1, -2, -1, -2};
const int dc[8] = {2, 1, -2, -1, 2, 1, -2, -1};

int main() {
int T;
char s[99];
gets(s);
sscanf(s, "%d", &T);
while (T--) {
int M, N;
gets(s);
sscanf(s, "%d%d", &M, &N);
bool block[100][100] = {};
P start, end;
for (int r = 0; r < M; r++) {
gets(s);
for (int c = 0; s[c]; c++) {
if (s[c] == 'A') {
start = MP(r, c);
block[r][c] = true;
} else if (s[c] == 'B') {
end = MP(r, c);
} else if (s[c] == 'Z') {
block[r][c] = true;
for (int i = 0; i < 8; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < M && nc >= 0 && nc < N) {
block[nr][nc] = true;
}
}
}
}
}
block[end.first][end.second] = false;
queue<P> q;
q.push(start);
bool find = false;
int dis[100][100] = {};
while (!q.empty()) {
P now = q.front();
int r = now.first, c = now.second;
int d = dis[r][c];
q.pop();
if (now == end) {
printf("Minimal possible length of a trip is %d\n", d);
find = true;
break;
}
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (!i && !j) {
continue;
}
int nr = r + i, nc = c + j;
if (nr >= 0 && nr < M && nc >= 0 && nc < N && !block[nr][nc]) {
q.push(MP(nr, nc));
dis[nr][nc] = d + 1;
block[nr][nc] = true;
}
}
}
}
if (!find) {
puts("King Peter, you can't go now!");
}
}
return 0;
}