BFS 80pts求调

评测记录

#include<bits/stdc++.h>
using namespace std;
int n,dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0},d[10001][4],begx,begy,endx,endy,ans;
char MAP[119][110];
bool b[110][110];
void bfs(){
    int head=0,tail=1,tx,ty;
    d[1][0]=-1;
    d[1][1]=begx,d[1][2]=begy;
    b[begx][begy]=1;
    while(head<tail){
        ++head;
        for(int i=1;i<=4;i++){
            tx=d[head][1]+dx[i];
            ty=d[head][2]+dy[i];
            while(b[tx][ty]==0&&tx>0&&tx<=n&&ty>0&&ty<=n&&MAP[tx][ty]=='.'){
                ++tail;
                b[tx][ty]=1;
                d[tail][1]=tx;
                d[tail][2]=ty;
                d[tail][0]=d[head][0]+1;
                if(tx==endx&&ty==endy){
                    printf("%d\n",d[tail][0]);
                    exit(0);
                }
                tx=d[tail][1]+dx[i];
                ty=d[tail][2]+dy[i];
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>MAP[i][j];
            if(MAP[i][j]=='A') begx=i,begy=j,MAP[i][j]='.';
            if(MAP[i][j]=='B') endx=i,endy=j,MAP[i][j]='.';
        }
    bfs();
}