这一题我们考虑一个最裸的算法：
我们设$dp[i][j][k][l]$表示当前棋子在$(i,j)$且空格在$(k,l)$时的最小步数
然后显然随便转移一下就好了，时间复杂度为$O(q(nm)^2)$。可以获得$80$分的好成绩（我自测的时候只打了这个）
我们发现这一题有一些很优秀的性质：
首先整个图是静态的，且起点，终点，出现空格的位置均非障碍物。
那么对于这个性质，我们做一些微小的预处理。
考虑到当空格与目标棋子四相邻的时候，棋子才能往空格内移动。那么整个走棋的过程可以理解为：调整空格位置-移动棋子到空格里-调整空格位置
我们设$f[i][j][k][l]$表示在不经过$(i,j)$的情况下，将空格从$(i+wx[k],j+wy[k])$移动到$(i+wx[l],j+wy[l])$的最小步数，其中$wx,wy$满足$|wx[i]+wy[i]|=1$，显然有四种组合。
对于每一个$f[i][j][k][l]$，我们通过一次$bfs$去求解。
预处理$f$的时间复杂度显然为$O(16nm)$。
下面考虑每一组询问：
若起点和终点的坐标相同，那么显然输出$0$就好了。
若起点和终点坐标不相同，我们先考虑将空格移动到起点四相邻的位置，所需要的最小步数显然可以通过一次$bfs$求得。
然后我们设$d[i][j][k]$表示当前棋子在$(i,j)$时，空格在$(i+wx[k],j+wy[k])$的最小步数。
显然随便$bfs$就可以进行更新了。最后的答案显然是$min(d[tx][ty][])$。
时间复杂度$O(16nm+4qnm)$。跑得飞快。
#include<bits/stdc++.h>
#define M 32
#define INF 16843009
using namespace std;
int n,m,q,mp[M][M]={},dis[M][M]={},d[M][M][]={},f[M][M][][]={};
const int wx[]={,,,-};
const int wy[]={,,-,};
queue<int> qx,qy,qk;
void bfs(int X,int Y){
memset(dis,,sizeof(dis));
qx.push(X); qy.push(Y); dis[X][Y]=;
while(!qx.empty()){
X=qx.front(); qx.pop();
Y=qy.front(); qy.pop();
for(int i=;i<;i++){
int _x=X+wx[i],_y=Y+wy[i];
if(mp[_x][_y]&&dis[_x][_y]>dis[X][Y]+){
dis[_x][_y]=dis[X][Y]+;
qx.push(_x); qy.push(_y);
}
}
}
}
void move(int x,int y){
memset(dis,,sizeof(dis));
qx.push(x); qy.push(y); dis[x][y]=;
while(!qx.empty()){
x=qx.front(); qx.pop();
y=qy.front(); qy.pop();
for(int i=;i<;i++){
int _x=x+wx[i],_y=y+wy[i];
if(mp[_x][_y]&&dis[_x][_y]>dis[x][y]+){
dis[_x][_y]=dis[x][y]+;
qx.push(_x); qy.push(_y);
}
}
}
} void bfs(){
while(!qx.empty()){
int x=qx.front(); qx.pop();
int y=qy.front(); qy.pop();
int k=qk.front(); qk.pop();
for(int i=;i<;i++){
int _x=x+wx[i],_y=y+wy[i];
if(mp[_x][_y]==) continue;
if(d[_x][_y][(i+)&]>d[x][y][k]+f[x][y][k][i]+){
d[_x][_y][(i+)&]=d[x][y][k]+f[x][y][k][i]+;
qx.push(_x); qy.push(_y); qk.push((i+)&);
}
}
}
} int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) scanf("%d",&mp[i][j]); for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]){
mp[i][j]=;
for(int k=;k<;k++)
if(mp[i+wx[k]][j+wy[k]]){
bfs(i+wx[k],j+wy[k]);
for(int l=;l<;l++)
f[i][j][k][l]=dis[i+wx[l]][j+wy[l]];
}
mp[i][j]=;
} while(q--){
int ex,ey,sx,sy,tx,ty;
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){
printf("0\n");
continue;
}
mp[sx][sy]=;
move(ex,ey);
mp[sx][sy]=;
memset(d,,sizeof(d));
for(int i=;i<;i++)
if(mp[sx+wx[i]][sy+wy[i]]){
qx.push(sx);
qy.push(sy);
qk.push(i);
d[sx][sy][i]=dis[sx+wx[i]][sy+wy[i]];
}
bfs();
int minn=INF;
for(int i=;i<;i++)
minn=min(minn,d[tx][ty][i]);
if(minn==INF) printf("-1\n");
else cout<<minn<<endl;
}
}