[NOIP2013]华容道 题解（搜索）

 [NOIP2013]华容道

【题目描述】

　　这道题根据小时候玩华容道不靠谱的经验还以为是并查集，果断扑街。考后想想也是，数据这么小一定有他的道理。

　　首先由于是最小步数，所以BFS没跑了。那么我们大可把这道题分为两部分，首先先把白格子移到目标棋子附近，然后再把目标棋子移过去。第一步是很容易的，随便BFS一下就好了，关键是第二步。由于q不小，我们不可能每次询问都直接爆搜，但由于棋盘并不会发生本质改变，我们可以对一些东西进行预处理。

　　那每次询问时不变的是什么呢，我们求第二步时需要的又是什么呢？

　　首先我们可以明确的是一个棋子得以移动一定是它移动的目标上是空的，而我们只有一个空格子，所以一旦我们确定了空格子的位置整个棋盘的状态就明了了，所以我们要处理的是当白格子在哪个位置时我想把当前棋子移到上下左右某一位置所要花费的最少步数，那么我们真的需要开5维去表示这一状态吗？不必，四维就够了，对于白格子从之前道这个点附近其实本质和第一步无异，而在我们执行第二步时白格子在每次转移完一定是在目标棋子的上下左右位置，所以我们只需要处理出来目标棋子在当前格子时白格子在他上下左右时他向上下左右移动所耗费的步数即可。

　　然后，对于每一次询问，我们可以把每个点拆成四个，即白格子在这个点上下左右时的最小步数，慢慢搞即可。

　　对了，提醒一下，对于某个格子进行处理的时候一定不能通过该点进行更新。

　　

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
int n,m,q,a[40][40],zy[5][2],dis[40][40];
struct no{int x,y,k;};
bool check(int x,int y,int z){
    if(x+zy[z][0]!=0&&x+zy[z][0]!=n+1&&y+zy[z][1]!=0&&y+zy[z][1]!=m+1&&a[x+zy[z][0]][y+zy[z][1]]) return 1;
    return 0;
}
bool fw[40][40],f2[40][40];
int f[40][40][5][5];
void bfs1(int ax,int by){
    memset(dis,0x3f,sizeof(dis));
    memset(fw,0,sizeof(fw));
    queue<no> q1;
    no aa;
    aa.x=ax,aa.y=by;
    dis[ax][by]=0;
    q1.push(aa);
    fw[ax][by]=1;
    while(!q1.empty())
    {
        no t=q1.front();
        q1.pop();
        int x=t.x,y=t.y;
        for(int i=1;i<=4;i++)
        {
            int xx=x+zy[i][0],yy=y+zy[i][1];
            if(xx==0||xx==n+1||yy==0||yy==m+1) continue;
            if(!a[xx][yy]) continue;
            if(f2[xx][yy]) continue;
            if(dis[xx][yy]>dis[x][y]+1)
            {
                dis[xx][yy]=dis[x][y]+1;
                if(!fw[xx][yy])
                {
                    fw[xx][yy]=1;
                    no bb;
                    bb.x=xx,bb.y=yy;
                    q1.push(bb);
                }
            }
        }
    }
}
bool rd[40][40][4];
int dis2[40][40][5];
void spfa(int ax,int by){
    memset(rd,0,sizeof(rd));
    no aa;
    queue<no> q1;
    aa.x=ax,aa.y=by;
    if(check(ax,by,1))
    {   
        aa.k=1;
        q1.push(aa);
        rd[ax][by][1]=1;
    }
    if(check(ax,by,2))
    {
        aa.k=2;
        q1.push(aa);
        rd[ax][by][2]=1;
    }
    if(check(ax,by,3))
    {
        aa.k=3;
        q1.push(aa);
        rd[ax][by][3]=1;
    }
    if(check(ax,by,4))
    {
        aa.k=4;
        q1.push(aa);
        rd[ax][by][4]=1;
    }
    while(!q1.empty())
    {
        no bb=q1.front();q1.pop();
        int x=bb.x,y=bb.y,k=bb.k;
        rd[x][y][k]=0;
        if(check(x,y,1)&&dis2[x-1][y][2]>dis2[x][y][k]+f[x][y][1][k]&&f[x][y][1][k]!=-1)
        {
            dis2[x-1][y][2]=dis2[x][y][k]+f[x][y][1][k];
            if(!rd[x-1][y][2])
            {
                rd[x-1][y][2]=1;
                no cc;
                cc.x=x-1,cc.y=y,cc.k=2;
                q1.push(cc);
            }
        }
        if(check(x,y,2)&&dis2[x+1][y][1]>dis2[x][y][k]+f[x][y][2][k]&&f[x][y][2][k]!=-1)
        {
            dis2[x+1][y][1]=dis2[x][y][k]+f[x][y][2][k];
            if(!rd[x+1][y][1])
            {
                rd[x+1][y][1]=1;
                no cc;
                cc.x=x+1,cc.y=y,cc.k=1;
                q1.push(cc);
            }
        }
        if(check(x,y,3)&&dis2[x][y-1][4]>dis2[x][y][k]+f[x][y][3][k]&&f[x][y][3][k]!=-1)
        {
            dis2[x][y-1][4]=dis2[x][y][k]+f[x][y][3][k];
            if(!rd[x][y-1][4])
            {
                rd[x][y-1][4]=1;
                no cc;
                cc.x=x,cc.y=y-1,cc.k=4;
                q1.push(cc);
            }
        }
        if(check(x,y,4)&&dis2[x][y+1][3]>dis2[x][y][k]+f[x][y][4][k]&&f[x][y][4][k]!=-1)
        {
            dis2[x][y+1][3]=dis2[x][y][k]+f[x][y][4][k];
            if(!rd[x][y+1][3])
            {
                rd[x][y+1][3]=1;
                no cc;
                cc.x=x,cc.y=y+1,cc.k=3;
                q1.push(cc);
            }
        }
    }
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    zy[1][0]=-1,zy[2][0]=1;
    zy[3][1]=-1,zy[4][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!a[i][j]) continue;
            f2[i][j]=1;
            for(int k=1;k<=4;k++)
            {      
                if(check(i,j,k))
                {
                    bfs1(i+zy[k][0],j+zy[k][1]);
                    for(int l=1;l<=4;l++)
                    {
                        if(check(i,j,l)&&dis[i+zy[l][0]][j+zy[l][1]]!=dis[0][0])
                            f[i][j][l][k]=dis[i+zy[l][0]][j+zy[l][1]]+1;
                    }
                }
            }
            f2[i][j]=0;
        }
    }
     
    for(int i=1;i<=q;i++)
    {
        int ex,ey,sx,sy,tx,ty;
        scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
        if(tx==sx&&ty==sy)
        {
            printf("0
");
            continue;
        }
        memset(dis2,0x3f,sizeof(dis2));
        memset(f2,0,sizeof(f2));
        f2[sx][sy]=1;
        bfs1(ex,ey);
        bool yx=0;
        for(int j=1;j<=4;j++)
        {
            if(check(sx,sy,j)&&dis[sx+zy[j][0]][sy+zy[j][1]]!=dis[0][0])
            {
                yx=1;
                dis2[sx][sy][j]=dis[sx+zy[j][0]][sy+zy[j][1]];
            }
        }
        if(!yx)
        {
            printf("-1
");
            continue;
        }
        spfa(sx,sy);
        int ans=0x7fffffff;
        for(int j=1;j<=4;j++)
            ans=min(ans,dis2[tx][ty][j]);
        if(ans==0x7fffffff||ans==dis2[0][0][0])
        {
            printf("-1
");
            continue;
        }
        else
            printf("%d
",ans);
    }
    return 0;
}