80求助,在线等,急

P1649 [USACO07OCT] Obstacle Course S

小鼬子 @ 2018-10-18 19:36:53

#include<bits/stdc++.h>
using namespace std;
int n,a[104][104],b[104][104],x0,y00,xd,yd,ans=99999999,lx[10010],ly[10010],tail=1,head=1;
char in;
void zou(int x,int y)
{   int j=b[x][y];
    if(a[x+1][y]>a[x][y])
                     {a[x+1][y]=a[x][y];
                      if(j!=1)a[x+1][y]++;
                      if(x+1==xd&&y==yd){ans=min(ans,a[x+1][y]);a[x+1][y]=99999999;}
                      else{lx[tail]=x+1;ly[tail++]=y;b[x+1][y]=1;}}
    if(a[x][y+1]>a[x][y])
                     {a[x][y+1]=a[x][y];
                      if(j!=2)a[x][y+1]++;
                      if(x==xd&&y+1==yd){ans=min(ans,a[x][y+1]);a[x][y+1]=99999999;}
                      else{lx[tail]=x;ly[tail++]=y+1;b[x][y+1]=2;}}
    if(a[x][y-1]>a[x][y])
                     {a[x][y-1]=a[x][y];
                      if(j!=3)a[x][y-1]++;
                      if(x==xd&&y-1==yd){ans=min(ans,a[x][y-1]);a[x][y-1]=99999999;}
                      else{lx[tail]=x;ly[tail++]=y-1;b[x][y-1]=3;}}
    if(a[x-1][y]>a[x][y])
                     {a[x-1][y]=a[x][y];
                      if(j!=4)a[x-1][y]++;
                      if(x-1==xd&&y==yd){ans=min(ans,a[x-1][y]);a[x-1][y]=99999999;}
                      lx[tail]=x-1;ly[tail++]=y;b[x-1][y]=4;}
                      return;
}
int main()
{cin>>n;
for(int i=1;i<=n;i++)
 for(int j=1;j<=n;j++)
  {cin>>in;
   if(in=='.') a[i][j]=99999999;
   else if(in=='A') x0=i,y00=j;
   else if(in=='B') xd=i,yd=j;
  }
 a[xd][yd]=99999999;a[x0][y00]=0;
 lx[tail]=x0;ly[tail++]=y00;
 while(head<tail)
 {
    zou(lx[head],ly[head]);
    head++;
 }
 if(ans==99999999){cout<<-1;return 0;}
 cout<<ans-1<<endl;
 /*for(int i=1;i<=n;i++)
  {for(int j=1;j<=n;j++) 
   printf("%d ",a[i][j]);cout<<endl;}
 */return 0;
}

by woshigou @ 2023-10-04 16:21:23

现在还在等吗


|