NOIP2013 华容道

本文移植自个人的原博客（原文）

题目链接

Luogu 1979

题目描述

题解

在本题中，真正可以自由移动的只有空格子，考虑对于指定格子的移动，必然是将空格格子移动到当前节点与目标节点的路径上，并将其于当前节点互换，重复以上过程直到当前节点与目标节点重合，以上过程用普通的BFS即可模拟。

但是本题中询问次数过多，实际上存在很多重复计算，可以考虑进行预处理优化。

由于每次都要将空格子移动到当前节点旁边，所以空格子的路径不能经过当前节点，否则将会导致答案不为最少时间，如果空格子的路径必须经过当前节点，则显然无解。（见样例2）那么可以设$f[x][y][k][h]$表示从$(x,y)$的$k$方向节点在不经过$(x,y)$的情况下移动到$h$方向节点的最小时间，对其进行预处理，然后每次询问通过SPFA求解即可。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define mp make_pair 
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N =31+1;
int n,m,Q,e1,e2,s1,s2,t1,t2;
int f[N][N][4][4],d[N][N],dis[N][N][5],a[N][N];
bool vis[N][N],in[N][N][5];
int fx[4]={-1,1,0,0};
int fy[4]={0,0,-1,1};
struct nd{
    int x,y,k;
};
queue<nd>q,q1;

int rev(int x){
    if(x==1)return 0;
    if(x==0)return 1;
    if(x==2)return 3;
    if(x==3)return 2;
}

int bfs(int x1,int y1,int x2,int y2){
    if(!a[x1][y1]||!a[x2][y2])return inf;
    memset(vis,0,sizeof(vis));
    memset(d,0x3f,sizeof(d));
    nd p;
    d[x1][y1]=0;
    vis[x1][y1]=1;
    while(!q1.empty())q1.pop();
    q1.push((nd){x1,y1,0});
    while(!q1.empty()&&!vis[x2][y2]){
        p=q1.front();q1.pop();
        for(int i=0;i<4;++i){
            int x=p.x+fx[i],y=p.y+fy[i];
            if(!vis[x][y]&&a[x][y]){
                vis[x][y]=1;
                d[x][y]=d[p.x][p.y]+1;
                q1.push((nd){x,y,0});
            }
        }
    }
    return d[x2][y2];
}

void init(){
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i)
    for(int t=1;t<=m;++t)
    if(a[i][t]){
        a[i][t]=0;
        for(int k=0;k<4;++k)
        for(int h=0;h<4;++h){
            if(h<k){f[i][t][k][h]=f[i][t][h][k];continue;}
            int x=i+fx[k],y=t+fy[k];
            int x11=i+fx[h],y11=t+fy[h];
            if(!a[x][y]||!a[x11][y11])continue;
            f[i][t][k][h]=bfs(x,y,x11,y11)+1;
//            cout<<i<<" "<<t<<" "<<f[i][t][k][h]<<endl;
        }
        a[i][t]=1;
    }
}

int spfa(int x1,int y1,int x2,int y2,int e1,int e2){
    if(x1==x2&&y1==y2)return 0;
    if(!a[x1][y1]||!a[x2][y2])return -1;
    memset(dis,0x3f,sizeof(dis));
    memset(in,0,sizeof(in));
    while(!q.empty())q.pop();
    a[x1][y1]=0;
    for(int k=0;k<4;++k){
        q.push((nd){x1,y1,k});
        in[x1][y1][k]=1;
        dis[x1][y1][k]=bfs(e1,e2,x1+fx[k],y1+fy[k]);
    }
    a[x1][y1]=1;
    nd x,y;
    while(!q.empty()){
        x=q.front();q.pop();
        in[x.x][x.y][x.k]=0;
        for(int h=0;h<4;++h){
            y.x=x.x+fx[h],y.y=x.y+fy[h];
            y.k=rev(h);
            if(dis[y.x][y.y][y.k]>dis[x.x][x.y][x.k]+f[x.x][x.y][x.k][h]){
                dis[y.x][y.y][y.k]=dis[x.x][x.y][x.k]+f[x.x][x.y][x.k][h];
                if(!in[y.x][y.y][y.k])in[y.x][y.y][y.k]=1,q.push(y);
            }
        }
    }
    int ret=inf;
    for(int i=0;i<4;++i)ret=min(ret,dis[x2][y2][i]);
    return ret<inf?ret:-1;
}
int main(){
    freopen("PuzzleNOIP2013.in","r",stdin);
    freopen("PuzzleNOIP2013.out","w",stdout);
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;++i)
    for(int t=1;t<=m;++t)
    scanf("%d",&a[i][t]);
    init();
    while(Q--){
        scanf("%d%d%d%d%d%d",&e1,&e2,&s1,&s2,&t1,&t2);
        int ans=0,tot=0;
        printf("%d\n",spfa(s1,s2,t1,t2,e1,e2));
        dddd:;
    }
}
/*
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
*/
/*


3 3 1
1 1 0
1 1 0
1 1 0
3 1 1 1 3 1


*/