1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include<iostream>
using namespace std;
int t, m, n, ans, que[100005][2], dis[105][105];
int H_dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int H_dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int K_dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int K_dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int start_x, start_y, end_x, end_y, cur_x, cur_y, nx, ny;
char arr[105][105], tmp;
bool vis[105][105];
int BFS(){
que[0][0] = start_x;
que[0][1] = start_y;
dis[start_x][start_y] = 0;
vis[start_x][start_y] = true;
for(int i=0, j=1 ; i<j ; i++){
cur_x = que[i][0];
cur_y = que[i][1];
if(cur_x == end_x && cur_y == end_y){
return dis[end_x][end_y];
}
for(int k=0 ; k<8 ; k++){
nx = cur_x + K_dx[k];
ny = cur_y + K_dy[k];
if(nx < 0 || nx >=m || ny < 0 || ny >= n) continue;
if(!vis[nx][ny] && arr[nx][ny] != '#'){
vis[nx][ny] = true;
dis[nx][ny] = dis[cur_x][cur_y] + 1;
que[j][0] = nx;
que[j][1] = ny;
j++;
}
}
}
return -1;
}
int main(){
cin>>t;
while(t--){
cin>>m>>n;
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<n ; j++){
arr[i][j] = '.';
vis[i][j] = false;
}
}
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<n ; j++){
cin>>tmp;
if(tmp == 'A'){
arr[i][j] = tmp;
start_x = i;
start_y = j;
}
else if(tmp == 'B'){
arr[i][j] = tmp;
end_x = i;
end_y = j;
}
else if(tmp == 'Z'){
arr[i][j] = '#';
for(int k=0 ; k<8 ; k++){
nx = i + H_dx[k];
ny = j + H_dy[k];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && arr[nx][ny] == '.'){
arr[nx][ny] = '#';
}
}
}
}
}
ans = BFS();
if(ans == -1){
cout<<"King Peter, you can't go now!\n";
}
else{
cout<<"Minimal possible length of a trip is "<<ans<<"\n";
}
}
return 0;
}
|