30分代码求助QAQ

P1649 [USACO07OCT] Obstacle Course S

眼镜犬 @ 2020-02-19 16:43:26


#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char c=getchar();int num=0;bool b=0;
    for(;c<'0'||c>'9';b=(c=='-'?1:0),c=getchar());
    for(;c>='0'&&c<='9';num=(num<<3)+(num<<1)+(c^'0'),c=getchar());
    return b?-num:num;
}
const int dx[]={1,0,-1,0};
const int dy[]={0,-1,0,1};
struct que{
    int step,x,y,xx,yy;
}a[100001]; 
char MAP[101][101],x;
bool vis[101][101];
int fx,fy;
int head,tail,ans=99999,n;
void bfs(int fx,int fy){
    a[tail].xx=fx;
    a[tail].yy=fy;
    a[tail].x=fx;
    a[tail].y=fy;
    a[tail].step=0;
    tail++;
    vis[fx][fy]=true;
    while(head<tail){
        for(int i=0;i<4;i++){
            int xx=a[head].x+dx[i];
            int yy=a[head].y+dy[i];
            if(xx<0||xx>n||yy<0||yy>n||vis[xx][yy]||MAP[xx][yy]=='x') continue;
            vis[xx][yy]=true;
            int cx=a[head].x-a[head].xx;
            int cy=a[head].y-a[head].yy;
            int flag=0;
            if((xx-a[head].x==cx)&&(yy-a[head].y==cy)) flag=0;
            else flag=1;
            a[tail].x=xx;
            a[tail].y=yy;
            a[tail].xx=a[head].x;
            a[tail].yy=a[head].y;
            a[tail].step=a[head].step+flag;
        //  cout<<xx<<" "<<yy<<endl;
            if(MAP[xx][yy]=='B') ans=min(ans,a[tail].step-1);
            tail++;
        }
        head++;
    }
}
int main(){
    n=read();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>x;
            if(x=='A'){
                fx=i;
                fy=j;
            }
            MAP[i][j]=x;
        }
    }
    bfs(fx,fy);
    if(ans==99999) printf("-1");
    else printf("%d",ans);
    return 0;
} 

|