JZYZOJ1442 [noip2013]华容道 bfs 最短路剪枝

http://172.20.6.3/Problem_Show.asp?id=1442

想到最短路的简直神了，如果我写我大概只能写一个30分的bfs。

从数据范围可以看出思路是bfs剪枝，但这里的剪枝是通过最短路的预处理实现的。

设需要移动的格子为a格子。

对求最小移动数有意义的移动只有两种，一种是空白格子的移动，一种是a格子移动到空白格子里。

可以得知要把空白格子移动到a格子旁边然后对a格子进行移动。

那么我们有了每次查找时进行的预处理1：求空白格子到a格子四周格子的最短路。

在模拟移动的过程中，可以发现a格子移动的方向是由其旁边的空白格子的位置决定的，对改变a格子移动方向有意义的步数是改变空白格子相对于a格子的方向的步数。

所以我们就有了预处理2：在查找前预处理出loc[x][y][i][j]，即空白格子从格子(x,y)的i方向移动到j方向的最短路。

需要注意的是，预处理1中求最短路是不能经过a格子所在位置的，同样，其他的bfs或最短路处理也要注意格子移动对所求格子位置的改变，避免改变所求格子位置的情况。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const long long modn=;

 int n,m,d;

 int e[][]={};

 int dis[][]={};

 int an[][][]={};

 int loc[][][][]={};

 int vis[][][]={};

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

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

 int ex,ey,sx,sy,tx,ty,ma;

 struct pa{

     int x;

     int y,w;

 };

 void getit(int xx,int yy){

     int x,y;

     queue<pa>q;

     pa z;

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

         z.x=xx+d1[i];

         z.y=yy+d2[i];

         memset(dis,,sizeof(dis));

         if(e[z.x][z.y]){

             dis[z.x][z.y]=;

             q.push(z);

         }

         while(!q.empty()){

             x=q.front().x;y=q.front().y;q.pop();

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

                 z.x=x+d1[i];

                 z.y=y+d2[i];

                 if(e[z.x][z.y]&&(z.x!=xx||z.y!=yy)&&dis[z.x][z.y]==ma){

                     dis[z.x][z.y]=dis[x][y]+;

                     q.push(z);

                 }

             }

         }

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

             int xx1,yy1;

             xx1=xx+d1[j];

             yy1=yy+d2[j];

             loc[xx][yy][i][j]=dis[xx1][yy1];

         }

     }

 }

 void pre(){

     pa z;

     queue<pa>q;

     memset(dis,,sizeof(dis));

     dis[ex][ey]=;

     z.x=ex;

     z.y=ey;

     q.push(z);

     int x,y;

     while(!q.empty()){

         x=q.front().x;y=q.front().y;q.pop();

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

             z.x=x+d1[i];

             z.y=y+d2[i];

             if(e[z.x][z.y]&&(z.x!=sx||z.y!=sy)&&dis[z.x][z.y]==ma){

                 dis[z.x][z.y]=dis[x][y]+;

                 q.push(z);

             }

         }

     }

 }

 int bfs(){

     if(sx==tx&&sy==ty)return ;

     pre();

     queue<pa>q;pa z;

     memset(an,,sizeof(an));

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

         z.x=sx+d1[i];

         z.y=sy+d2[i];

         z.w=i;

         if(e[z.x][z.y]&&dis[z.x][z.y]!=ma){

             an[sx][sy][i]=dis[z.x][z.y];

             z.x=sx;z.y=sy;

             vis[sx][sy][i]=;

             q.push(z);

         }

     }int x,y,w;

     while(!q.empty()){

         x=q.front().x;

         y=q.front().y;

         w=q.front().w;

         q.pop();

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

             if(i==w)continue;

             z.x=x;z.y=y;z.w=i;

             if(e[x+d1[w]][y+d2[w]]&&an[x][y][w]+loc[x][y][w][i]<an[x][y][i]){

                 an[x][y][i]=an[x][y][w]+loc[x][y][w][i];

                 if(!vis[x][y][i]){

                     vis[x][y][i]=;

                     q.push(z);

                 }

             }

         }

         z.x=x+d1[w];z.y=y+d2[w];

         if(w==)z.w=;

         else if(w==)z.w=;

         else if(w==)z.w=;

         else z.w=;

         if(an[x][y][w]+<an[z.x][z.y][z.w]){

             an[z.x][z.y][z.w]=an[x][y][w]+;

             if(!vis[z.x][z.y][z.w]){

                 vis[z.x][z.y][z.w]=;

                 q.push(z);

             }

         }

         vis[x][y][w]=;

     }

     int ans=ma;

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

         ans=min(ans,an[tx][ty][i]);

     }

     if(ans!=ma)return ans;

     return -;

 }

 int main(){

     //freopen("wtf.in","r",stdin);

     scanf("%d%d%d",&n,&m,&d);

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

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

             scanf("%d",&e[i][j]);

         }

     }memset(loc,,sizeof(loc));

     ma=loc[][][][];

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

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

             getit(i,j);

         }

     }

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

         scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);

         memset(vis,,sizeof(vis));

         printf("%d\n",bfs());

     }

     return ;

 }

巴特西

JZYZOJ1442 [noip2013]华容道 bfs 最短路剪枝

最新文章

热门文章

巴特西

JZYZOJ1442 [noip2013]华容道 bfs 最短路 剪枝

最新文章

热门文章

JZYZOJ1442 [noip2013]华容道 bfs 最短路剪枝