bzoj1644 / P1649 [USACO07OCT]障碍路线Obstacle Course

P1649 [USACO07OCT]障碍路线Obstacle Course

bfs

直接上个bfs

注意luogu的题目和bzoj有不同（bzoj保证有解，还有输入格式不同）。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 #define pi pair<int,int>

 #define mkp make_pair

 #define N 105

 const int d1[]={,,,-};

 const int d2[]={,,-,};

 char q[]; bool dan[N][N];

 int a[N][N],vis[N][N],n;

 pi S,T; queue<pi> h;

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j){

             scanf("%s",q);

             if(q[]=='A') S=mkp(i,j);

             if(q[]=='B') T=mkp(i,j);

             if(q[]=='x') dan[i][j]=;

         }

     }h.push(S);

     while(!h.empty()){

         pi u=h.front(); h.pop();

         for(int i=;i<;++i){

             int r1=u.first+d1[i],r2=u.second+d2[i];

             while(!dan[r1][r2]){

                 if(r1>n||r1<||r2>n||r2<) break;

                 if(vis[r1][r2]){

                     r1+=d1[i];r2+=d2[i];

                     continue;

                 }

                 vis[r1][r2]=vis[u.first][u.second]+;

                 if(mkp(r1,r2)==T){

                     printf("%d",max(,vis[r1][r2]-));

                     return ;

                 }h.push(mkp(r1,r2));

                 r1+=d1[i];r2+=d2[i];

             }

         }

     }printf("-1");

     return ;

 }

P1649

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 #define pi pair<int,int>

 #define mkp make_pair

 #define N 105

 const int d1[]={,,,-};

 const int d2[]={,,-,};

 char q[N]; bool dan[N][N];

 int a[N][N],vis[N][N],n;

 pi S,T; queue<pi> h;

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i){

         scanf("%s",q);

         for(int j=;j<=n;++j){

             if(q[j-]=='A') S=mkp(i,j);

             if(q[j-]=='B') T=mkp(i,j);

             if(q[j-]=='x') dan[i][j]=;

         }

     }h.push(S);

     while(!h.empty()){

         pi u=h.front(); h.pop();

         for(int i=;i<;++i){

             int r1=u.first+d1[i],r2=u.second+d2[i];

             while(!dan[r1][r2]){

                 if(r1>n||r1<||r2>n||r2<) break;

                 if(vis[r1][r2]){

                     r1+=d1[i];r2+=d2[i];

                     continue;

                 }vis[r1][r2]=vis[u.first][u.second]+;

                 if(mkp(r1,r2)==T){

                     printf("%d",max(,vis[r1][r2]-));

                     return ;

                 }h.push(mkp(r1,r2));

                 r1+=d1[i];r2+=d2[i];

             }

         }

     }

 }

bzoj1644