M_sea

洛谷1979 华容道
Luogu分析建个图乱搞首先可以把格子hash成id。然后利用Bfs建出状态图。最后求个最短路输出就好了。细节见代...
扫描右侧二维码阅读全文
26
2018/10

洛谷1979 华容道

Luogu

分析

建个图乱搞

首先可以把格子hash成id。

然后利用Bfs建出状态图。

最后求个最短路输出就好了。

细节见代码。

代码

去年写的qwq

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define re register
#define pii pair<int,int>
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<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int n,m,q;
const int mvx[4]={-1,1,0,0},mvy[4]={0,0,-1,1};
struct Edge { int v,w,nxt; } e[40010];
int head[4010],cnt=0;
inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int map[31][31],dis[31][31];
struct node { int x,y; };
inline int Hash(int x,int y,int fx) { return x*120+y*4+fx; }
inline void Bfs(int sx,int sy,int ex,int ey,int fx) {
    memset(dis,0,sizeof(dis));
    queue<node> Q; Q.push((node){sx,sy}); dis[sx][sy]=1;
    while (!Q.empty()) {
        node fr=Q.front(); Q.pop();
        int x=fr.x,y=fr.y;
        for (re int i=0;i<=3;i++) {
            int xx=x+mvx[i],yy=y+mvy[i];
            if (map[xx][yy]&&!dis[xx][yy]&&(xx!=ex||yy!=ey)) {
                dis[xx][yy]=dis[x][y]+1;
                Q.push((node){xx,yy});
            }
        }
    }
    if (fx==4) return;
    for (re int i=0;i<=3;i++) {
        int x=ex+mvx[i],y=ey+mvy[i];
        if ((x!=sx||y!=sy)&&dis[x][y])
            addEdge(Hash(ex,ey,fx),Hash(ex,ey,i),dis[x][y]-1);
    }
    addEdge(Hash(ex,ey,fx),sx*120+sy*4+fx^1,1);
}
int dis2[4010];
bool inq[4010];
inline void SPFA(int sx,int sy) {
    queue<int> Q;
    memset(dis2,0x3f3f3f3f,sizeof(dis2));
    memset(inq,false,sizeof(inq));
    for (re int i=0;i<=3;i++) {
        int x=sx+mvx[i],y=sy+mvy[i],num=Hash(sx,sy,i);
        if (dis[x][y]) { dis2[num]=dis[x][y]-1,Q.push(num); inq[num]=true; }
    }
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=false;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis2[u]+w<dis2[v]) {
                dis2[v]=dis2[u]+w;
                if (!inq[v]) { inq[v]=true; Q.push(v); }
            }
        }
    }
}
int main() {
    n=read(); m=read(); q=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++)
            map[i][j]=read();
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            if (!map[i][j]) continue;
            if (map[i-1][j]) Bfs(i-1,j,i,j,0);
            if (map[i+1][j]) Bfs(i+1,j,i,j,1);
            if (map[i][j-1]) Bfs(i,j-1,i,j,2);
            if (map[i][j+1]) Bfs(i,j+1,i,j,3);
        }
    for (re int i=1;i<=q;i++) {
        int sx,sy,ex,ey,wx,wy;
        wx=read(); wy=read(); sx=read(); sy=read(); ex=read(); ey=read();
        if (sx==ex&&sy==ey) { printf("0\n"); continue; }
        Bfs(wx,wy,sx,sy,4); SPFA(sx,sy); int ans=1061109567;
        for (re int i=0;i<=3;i++) ans=min(ans,dis2[Hash(ex,ey,i)]);
        if (ans!=1061109567) printf("%d\n",ans);
        else printf("-1\n");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 11 PM

发表评论