求助。。30分不知道怎么改了。。

P1649 [USACO07OCT] Obstacle Course S

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;
}

救救孩子吧,改了一晚上加一下午了。。


|