help 10pts BFS

P1649 [USACO07OCT] Obstacle Course S

蚂蚁名 @ 2022-05-05 19:44:05

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int s[10001][5],k=0,b[100001],k1,n,x2,y2,x3,y3,sum,f;
int dx[5]={0,-1,0,+1,0};
int dy[5]={0,0,+1,0,-1};
char a[1001][1001];
int a1[10001];
void mym(int x,int y)
{
    int h=0,t=1;
    a[x][y]='x';
    s[1][1]=x;
    s[1][2]=y;
    s[1][3]=0;
    while(h<t)
    {
        h++;
        for(int i=1;i<=4;i++)
        {
            int nx,ny;
            nx=s[h][1]+dx[i];
            ny=s[h][2]+dy[i]; 
            if(nx>=1 && nx<=5 && ny>=1 && ny<=5 && a[nx][ny]=='.')
            {
                t++;
                a[nx][ny]='x';
                s[t][1]=nx;
                s[t][2]=ny;
                s[t][3]=h;
                s[t][4]=i;
                if(nx==x3 && ny==y3)
                {
                    while(t>=1)
                    {
                        k++;
                        b[k]=t;
                        t=s[t][3];
                    }
                    for(int q=k;q>=1;q--)
                        a1[++k1]=s[b[q]][1];
                    return;
                }
            }
         }
    }
    cout<<-1;f=1;return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='A'){x2=i;y2=j;}
            if(a[i][j]=='B'){x3=i;y3=j;a[i][j]='.';}
        }
    }   
    mym(x2,y2);
    if(f==0)
    {
        for(int i=1;i<=k1-1;i++)
        if(abs(a1[i+1]-a1[i])==1)sum++;
        cout<<sum;
    }
    return 0;
}

|