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 <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
struct {
int v,cost,_next;
};
Edge edge[2000005];
int cnt=0,at[40005],n,V;
int d[40005],in[40005],que[500005],f=0,r=0;
void spfa_bfs(int s){
fill(d+1,d+4*V+1,INF);
for(int i=0;i<4;i++)
d[s+i*V]=0,in[s+i*V]=1,que[r++]=s+i*V;
int i,_u,_v,_co;
while(r-f){
_u=que[f++],in[_u]=0;
for(i=at[_u];i!=-1;i=edge[i]._next){
_v=edge[i].v,_co=edge[i].cost;
if(d[_u]+_co<d[_v]){
d[_v]=d[_u]+_co;
if(!in[_v]){
in[_v]=1,que[r++]=_v;
}
}
}
}
}
void addedge(int _u,int _v,int _cost){
edge[cnt].v=_v,
edge[cnt].cost=_cost,
edge[cnt]._next=at[_u],
at[_u]=cnt++;
}
int xa,xb,ya,yb;
char mat[105][105];
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void init(){
n=read();
char ord[1005];
int tot,len;
for(int i=1;i<=n;i++){
fgets(ord,300,stdin);
len=strlen(ord),tot=1;
for(int j=0;j<len;j++)
if(!isspace(ord[j]))mat[i][tot++]=ord[j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mat[i][j]=='A')xa=i,ya=j;
else if(mat[i][j]=='B')xb=i,yb=j;
V=n*n;
memset(at,-1,sizeof(at));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(mat[i][j]=='x')
continue;
int id=(i-1)*n+j;
addedge(id,2*V+id,1),addedge(2*V+id,id,1),
addedge(id,V+id,2),addedge(V+id,id,2),
addedge(id,3*V+id,1),addedge(3*V+id,id,1),
addedge(2*V+id,V+id,1),addedge(V+id,2*V+id,1),
addedge(3*V+id,V+id,1),addedge(V+id,3*V+id,1),
addedge(2*V+id,3*V+id,2),addedge(3*V+id,2*V+id,2);
if(i!=1&&mat[i-1][j]!='x')addedge(id,id-n,0);
if(i!=n&&mat[i+1][j]!='x')addedge(V+id,V+(id+n),0);
if(j!=1&&mat[i][j-1]!='x')addedge(2*V+id,2*V+(id-1),0);
if(j!=n&&mat[i][j+1]!='x')addedge(3*V+id,3*V+(id+1),0);
}
}
void solve(){
int id=(xa-1)*n+ya;
spfa_bfs(id);
id=(xb-1)*n+yb;
int ans=min(min(min(d[id],d[V+id]),d[2*V+id]),d[3*V+id]);
printf("%dn",ans==INF?-1:ans);
}
int main(){
init();
solve();
return 0;
}
|
近期评论