这道题中,棋子的移动是要移动到空格上去,所以空格要在棋子旁边才能移动棋子;而棋子移动的方向由空格决定
所以我们可以记三维状态(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
",ans<inf?ans:-1);
}
return 0;
}