考虑从起点到终点的过程，一定是先将空格子移到指定格子旁边，和指定格子交换，再移到下一个指定格子要到的地方，再交换，如此反复。
于是问题分为两个部分：
1.给定两个曼哈顿距离为2的格子求最短路，BFS即可。
2.根据1的结果决定从起点到终点的路径，使用SPFA求解。
其中，第一个问题空格子显然不能经过指定格子，BFS过程中需要特判。第二个问题的状态为(x,y,k)，表示当前指定格子在(x,y)，空格子在它的哪个方向(1<=k<=4)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,inf=1e9;
const int dx[]={-,,,},dy[]={,,-,};
bool inq[<<],mp[N][N];
int n,m,Q,ex,ey,sx,sy,tx,ty,d[<<],dis[N][N],cost[<<];
struct P{ int x,y; }q[<<];
struct S{ int x,y,dir; }q2[<<]; int F(int x,int y,int a,int b){ return x<< | y<< | a<< | b; }
int F(int x,int y,int k){ return x<< | y<< | k; } void bfs(int x0,int y0,int x1,int y1){
memset(dis,-,sizeof(dis));
mp[x1][y1]=; int st=,ed=,tot=; q[]=(P){x0,y0}; dis[x0][y0]=;
while (st<ed){
int x=q[++st].x,y=q[st].y;
if (abs(x-x1)+abs(y-y1)==)
if (--tot==) break;
rep(k,,){
int x2=x+dx[k],y2=y+dy[k];
if (mp[x2][y2] && dis[x2][y2]==-)
dis[x2][y2]=dis[x][y]+,q[++ed]=(P){x2,y2};
}
}
mp[x1][y1]=;
} void init(){
rep(i,,n) rep(j,,m) if (mp[i][j])
rep(p,,){
int x1=i+dx[p],y1=j+dy[p];
if (!mp[x1][y1]) continue;
bfs(i,j,x1,y1);
rep(q,,){
int x2=x1+dx[q],y2=y1+dy[q];
if (~dis[x2][y2]) cost[F(x1,y1,p^,q)]=dis[x2][y2]+;
}
}
} int spfa(){
int st=,ed=;
memset(d,0x3f,sizeof(d));
bfs(ex,ey,sx,sy);
rep(k,,){
int x1=sx+dx[k],y1=sy+dy[k];
if (dis[x1][y1]==-) continue;
q2[++ed]=(S){sx,sy,k}; d[F(sx,sy,k)]=dis[x1][y1]; inq[F(sx,sy,k)]=;
}
while (st<ed){
int x=q2[++st].x,y=q2[st].y,dir=q2[st].dir,u=F(x,y,dir); inq[u]=;
rep(k,,){
int x1=x+dx[k],y1=y+dy[k],c=cost[F(x,y,dir,k)],v=F(x1,y1,k^);
if (mp[x1][y1] && c && d[v]>d[u]+c){
d[v]=d[u]+c; if (!inq[v]) q2[++ed]=(S){x1,y1,k^},inq[v]=;
}
}
}
int ans=inf;
rep(k,,) ans=min(ans,d[F(tx,ty,k)]);
return ans==inf ? - : ans;
} int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
rep(i,,n) rep(j,,m) scanf("%d",&mp[i][j]);
init();
while (Q--){
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if (sx==tx && sy==ty) { puts(""); continue; }
printf("%d\n",spfa());
}
return ;
}