洛谷1979 华容道

Luogu

分析

我们设 $p(x,y,d)$ 表示白格在 $(x,y)$ 的 $d$ 方向。

首先,我们建出一张图,其中只有 $p(x,y,d)\to p(x,y,d')$ 的边以及​ $p(x,y,d)\to p(x+dx_d,y+dy_d,d_r)$ 的边。这里的 $dx_d$ 和 $dy_d$ 表示 $d$ 方向 $x$ 和 $y$ 的增量,$d_r$ 表示 $d$ 的反方向。

具体的建图过程可以直接 BFS。

然后考虑处理询问。首先我们要将白格移到 $(sx,sy)$ 的四周的某个位置,所以先从 $(ex,ey)$ 开始 BFS 一次;然后以 $(sx,sy)$ 四周的点为起点跑一遍 SPFA 即可。

注意特判一下 $(sx,sy)=(tx,ty)$ 的情况。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30+10;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
const int inf=0x3f3f3f3f;

int n,m,q,a[N][N];
int wdis[N][N],dis[N*N*4],inq[N*N*4];

struct edge { int v,w,nxt; } e[N*N*16];
int head[N*N*4];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
    
inline int id(int x,int y,int d) { return x*120+y*4+d; }

inline void bfs(int sx,int sy,int ex,int ey,int ed) {
    memset(wdis,-1,sizeof(wdis)); queue<pair<int,int> > Q;
    Q.push(make_pair(sx,sy)),wdis[sx][sy]=0;
    while (!Q.empty()) {
        int x=Q.front().first,y=Q.front().second; Q.pop();
        for (re int d=0;d<4;++d) {
            int X=x+dx[d],Y=y+dy[d];
            if (!a[X][Y]||(X==ex&&Y==ey)||(~wdis[X][Y])) continue;
            wdis[X][Y]=wdis[x][y]+1,Q.push(make_pair(X,Y));
        }
    }
    if (ed==-1) return;
    for (re int d=0;d<4;++d) {
        int X=ex+dx[d],Y=ey+dy[d];
        if (wdis[X][Y]==-1||(X==sx&&Y==sy)) continue;
        addEdge(id(ex,ey,ed),id(ex,ey,d),wdis[X][Y]);
    }
    addEdge(id(ex,ey,ed),id(sx,sy,ed^1),1);
}

inline void spfa(int sx,int sy) {
    memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)); queue<int> Q;
    for (re int d=0;d<4;++d) {
        int X=sx+dx[d],Y=sy+dy[d],u=id(sx,sy,d);
        if (~wdis[X][Y]) Q.push(u),dis[u]=wdis[X][Y],inq[u]=1;
    }
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
}

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            a[i][j]=read();
    for (re int x=1;x<=n;++x)
        for (re int y=1;y<=m;++y) {
            if (!a[x][y]) continue;
            for (re int d=0;d<4;++d)
                if (a[x+dx[d]][y+dy[d]]) bfs(x+dx[d],y+dy[d],x,y,d);
        }
    while (q--) {
        int ex=read(),ey=read(),sx=read(),sy=read(),tx=read(),ty=read();
        if (sx==tx&&sy==ty) { puts("0"); continue; }
        bfs(ex,ey,sx,sy,-1),spfa(sx,sy);
        int ans=inf;
        for (re int d=0;d<4;++d) ans=min(ans,dis[id(tx,ty,d)]);
        printf("%d\n",ans==inf?-1:ans);
    }
    return 0;
}
最后修改:2019 年 10 月 28 日 10 : 13 PM

发表评论