linlin @ 2019-10-01 16:39:49
#include<iostream>
#include<queue>
using namespace std;
char map[110][110];
bool vis[110][110][4]={0};
int vx[]={0,1,0,-1},vy[]={1,0,-1,0};//上右下左
int n;
struct node{
int x,y,to,time;
node(int x=0,int y=0,int to=0,int time=0):x(x),y(y),to(to),time(time){}
};
queue<node> q;
node start;
bool check(int x,int y,int t)
{
if(vis[x][y][t])
return 0;
if(map[x][y]=='x')
return 0;
if(x<1||x>n||y<1||y>n)
return 0;
return true;
}
int bfs()
{
int min=99999999;
while(!q.empty())
{
node u=q.front();
q.pop();
if(map[u.x][u.y]=='B')
if(u.time<min)
{
min=u.time;
continue;
}
int ccto=u.to;
for(int i=0;i<4;i++)
{
if((ccto==0&&i==2)||(ccto==1&&i==3)||(ccto==2&&i==0)||(ccto==3&&i==1))continue;
int px=u.x+vx[i],py=u.y+vy[i],pto=i,ptime=u.time;
if(check(px,py,pto))
{
//cout<<px<<' '<<py<<" "<<pto<<" "<<ptime<<" "<<endl;
if(pto!=u.to) {
ptime++;
}
q.push(node(px,py,pto,ptime));
vis[px][py][pto]=true;
}
}
}
return min;
}
int main()
{
int sx,sy;
cin>>n;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>map[i][j];
if(map[i][j]=='A')
{
sx=i;sy=j;
}
}
vis[sx][sy][0]=true;vis[sx][sy][1]=true;vis[sx][sy][2]=true;vis[sx][sy][3]=true;
for(i=0;i<4;i++)
{
start.x=sx+vx[i];start.y=sy+vy[i];start.to=i;start.time=0;
if(check(start.x,start.y,start.to))
{
q.push(start);
vis[start.x][start.y][start.to]=true;
}
}
int ans=bfs();
if(ans!=99999999)cout<<ans<<endl;
else cout<<"-1"<<endl;
return 0;
}
救救孩子吧,改了一晚上加一下午了。。