luogu P1979 [NOIP2013] 华容道

时间：2023-03-09 18:33:03
luogu P1979 [NOIP2013] 华容道

传送门

这道题中,棋子的移动是要移动到空格上去,所以空格要在棋子旁边才能移动棋子;而棋子移动的方向由空格决定

所以我们可以记三维状态\(di_{i,j,k}\),表示状态为棋子在\((i,j)\),空格在棋子\(k\)方向(顺时针编号0到3)上的最短距离

要\(bfs\)预处理\(mv_{i,j,k,l}\),表示不动\((i,j)\),把空格从\(k\)方向移到\(l\)方向的最短距离.转移时枚举棋子要走的方向\(l\),然后要把空格移到棋子\(l\)方向,再让棋子走上去,注意走完后空格会在棋子的\((l+2)\ mod\ 4\)方向,所以\(di_{i1,j1,(l+2)\ mod\ 4}=di_{i,j,k}+mv_{i,j,k,l}+1\)

转移的话推荐用\(spfa\)(我\(spfa\)还活着,,,_ (: 」∠) _)等最短路算法

还有处理初始状态时,要把空格先移动到棋子对应方向上

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define inf 1061109567

using namespace std;

const int N=40,M=20000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[M<<1],nt[M<<1],w[M<<1],hd[M],tot=1;

il void add(int x,int y,int z){++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;}

int mm[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int n,m,q,a[N][N],nxt[4]={2,3,0,1}; //nxt[i]=(i+2)%4

int mv[N][N][4][4];

int id[N][N][4],di[M];

int vis[N][N],ti;

bool v[M];

struct nnn

{

  int sx,sy,f,d;

};

int gdis(int x,int y,int tx,int ty,int d)

{

  vis[x][y]=ti;

  queue<nnn> q;

  q.push((nnn){x,y,0,0});

  while(!q.empty())

    {

      x=q.front().sx,y=q.front().sy,d=q.front().d;

      q.pop();

      if(x==tx&&y==ty) return d;

      for(int j=0;j<4;j++)

        {

          int xx=x+mm[j][0],yy=y+mm[j][1];

          if(vis[xx][yy]<ti&&a[xx][yy]) vis[xx][yy]=ti,q.push((nnn){xx,yy,0,d+1});

        }

    }

  return inf;

}

int main()

{

  n=rd(),m=rd(),q=rd();

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

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

      for(int k=0;k<4;k++)

        id[i][j][k]=(((i-1)*m+j)<<2)+k;

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

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

      a[i][j]=rd();

  memset(mv,63,sizeof(mv));

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

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

      {

        if(!a[i][j]) continue;

        for(int k=0;k<4;k++)

          {

            if(!a[i+mm[k][0]][j+mm[k][1]]) continue;

            for(int l=0;l<4;l++)

              {

                if(!a[i+mm[l][0]][j+mm[l][1]]) continue;

                if(k==l) {mv[i][j][k][l]=0;continue;}

                a[i][j]=0,++ti,mv[i][j][k][l]=gdis(i+mm[k][0],j+mm[k][1],i+mm[l][0],j+mm[l][1],0),a[i][j]=1;

              }

          }

      }

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

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

      for(int k=0;k<4;k++)

        for(int l=0;l<4;l++)

          add(id[i][j][k],id[i+mm[l][0]][j+mm[l][1]][nxt[l]],mv[i][j][k][l]+1);

  while(q--)

    {

      int ex=rd(),ey=rd(),sx=rd(),sy=rd(),tx=rd(),ty=rd();

      if(sx==tx&&sy==ty) {puts("0");continue;}

      memset(di,63,sizeof(di));

      queue<int> q;

      a[sx][sy]=0;

      for(int j=0;j<4;j++) ++ti,di[id[sx][sy][j]]=gdis(ex,ey,sx+mm[j][0],sy+mm[j][1],0),q.push(id[sx][sy][j]);

      a[sx][sy]=1;

      while(!q.empty())

        {

          int x=q.front();

          q.pop();

          for(int i=hd[x];i;i=nt[i])

            {

              int y=to[i];

              if(di[y]>di[x]+w[i])

                {

                  di[y]=di[x]+w[i];

                  if(!v[y]) q.push(y);

                  v[y]=true;

                }

            }

          v[x]=false;

        }

      int ans=min(min(di[id[tx][ty][0]],di[id[tx][ty][1]]),min(di[id[tx][ty][2]],di[id[tx][ty][3]]));

      printf("%d\n",ans<inf?ans:-1);

    }

  return 0;

}

相关文章