我想动某个点的话，一定要先把空白点移动到这个点旁边，然后调换这个点和空白点，一直重复
那么，我们就可以记一些状态(x,y,s) （s={0,1},{0,-1},{1,0},{-1,0}），表示我要动的点在(x,y)，然后空白点在(x+s.x,y+s.y)
这样的话我们就可以建图：$(x,y,s)-1->(x+s.x,y+s.y,s^{-1})$ (s^{-1}表示一个相反的方向，比如如果s是右边的话，那它就是左边）
$(x,y,s)-C(x,y,s+s.x,y+s.y,x+i.x,y+i.y)->(x,y,i)$ 其中，C(a,b,c,d,e,f)表示我目前这个点在(a,b)，空白点在(c,d)，要把空白点挪到(e,f)的最小步数，而且挪的过程中不能经过(a,b)（要不然会把要动的那个点换走）
这样的话，就可以一边bfs算出C的值，一边跑最短路了。
然而复杂度$O(q*(mn)^2)$,过不去。
考虑预处理出C，直接做显然不行（$mn^3$），但其实我们要用到C的情况，都是空白点在要处理的点的旁边的，那它就可以压缩成(x,y,s,tx,ty)，是900*4*900的。
当然，一开始我们的空白点和要做的点并没有在一起，只要再单独bfs一下，先把空白点挪到它边上就可以了。
要注意有起始点和目标点相同的情况，要判掉。
#include<bits/stdc++.h>
#define pa pair<int,int>
#define pa2 pair<int,Node>
#define ll long long
using namespace std;
const int maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Node{
int x,y,s;
Node (int x1,int x2,int x3){x=x1,y=x2,s=x3;}
};
int f[maxn][maxn],N,M,Q,dis[maxn][maxn][][maxn][maxn],dis2[maxn][maxn][];
int step[][]={{,},{,-},{,},{-,}};
bool can[maxn][maxn],flag[maxn][maxn],flag2[maxn][maxn][];
queue<pa > q;
priority_queue<pa2,vector<pa2>,greater<pa2> > q2; bool operator < (Node a,Node b){return a.x<b.x;} int bfs1(int a,int b,int c,int x0,int y0){
memset(flag,,sizeof(flag));
while(!q.empty()) q.pop();q.push(make_pair(x0,y0));
dis[a][b][c][x0][y0]=;
while(!q.empty()){
int x=q.front().first,y=q.front().second;q.pop();
for(int i=;i<=;i++){
int xx=x+step[i][],yy=y+step[i][];
if(!flag[xx][yy]&&can[xx][yy]){
q.push(make_pair(xx,yy));
dis[a][b][c][xx][yy]=dis[a][b][c][x][y]+;
}
}flag[x][y]=;
}
} int dijkstra(int ex,int ey,int sx,int sy,int tx,int ty){
if(sx==tx&&sy==ty) return ;
memset(dis2,-,sizeof(dis2));memset(flag2,,sizeof(flag2));
while(!q2.empty()) q2.pop();
can[sx][sy]=;memset(dis[][][],-,sizeof(dis[][][]));
bfs1(,,,ex,ey);
for(int i=;i<=;i++){
int xx=sx+step[i][],yy=sy+step[i][];
if(dis[][][][xx][yy]!=-){
dis2[xx][yy][i^]=dis[][][][xx][yy]+;
q2.push(make_pair(dis2[xx][yy][i^],Node(xx,yy,i^)));
}
}can[sx][sy]=;
while(!q2.empty()){
Node p=q2.top().second;q2.pop();if(flag2[p.x][p.y][p.s]) continue;
for(int i=;i<=;i++){
int xx=p.x+step[i][],yy=p.y+step[i][];
if(dis[p.x][p.y][p.s][xx][yy]!=-){
if(dis2[xx][yy][i^]==-||dis2[xx][yy][i^]>dis[p.x][p.y][p.s][xx][yy]+dis2[p.x][p.y][p.s]+){
dis2[xx][yy][i^]=dis[p.x][p.y][p.s][xx][yy]+dis2[p.x][p.y][p.s]+;
q2.push(make_pair(dis2[xx][yy][i^],Node(xx,yy,i^)));
}
}
}flag2[p.x][p.y][p.s]=;
}int re=-;
for(int i=;i<=;i++){
if(dis2[tx][ty][i]==-) continue;
if(re==-) re=dis2[tx][ty][i];
else re=min(re,dis2[tx][ty][i]);
}return re;
} int main(){
int i,j,k;
N=rd(),M=rd();Q=rd();
for(i=;i<=N;i++){
for(j=;j<=M;j++) can[i][j]=rd();
}
memset(dis,-,sizeof(dis));
for(i=;i<=N;i++){
for(j=;j<=M;j++){
if(!can[i][j]) continue;can[i][j]=;
for(k=;k<=;k++){
int ii=i+step[k][],jj=j+step[k][];
if(can[ii][jj]) bfs1(i,j,k,ii,jj);
}can[i][j]=;
}
}
for(i=;i<=Q;i++){
int x1=rd(),x2=rd(),x3=rd(),x4=rd(),x5=rd(),x6=rd();
printf("%d\n",dijkstra(x1,x2,x3,x4,x5,x6));
}
return ;
}