我想动某个点的话，一定要先把空白点移动到这个点旁边，然后调换这个点和空白点，一直重复

那么，我们就可以记一些状态(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一下，先把空白点挪到它边上就可以了。

要注意有起始点和目标点相同的情况，要判掉。

1 #include
     
       2 #define pa pair
      
        3 #define pa2 pair
       
         4 #define ll long long 5 using namespace std; 6 const int maxn=33; 7  8 inline ll rd(){ 9     ll x=0;char c=getchar();int neg=1;10     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();}11     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();12     return x*neg;13 }14 15 struct Node{16     int x,y,s;17     Node (int x1,int x2,int x3){x=x1,y=x2,s=x3;}18 };19 int f[maxn][maxn],N,M,Q,dis[maxn][maxn][4][maxn][maxn],dis2[maxn][maxn][4];20 int step[4][2]={
   {
   0,1},{
   0,-1},{
   1,0},{-1,0}};21 bool can[maxn][maxn],flag[maxn][maxn],flag2[maxn][maxn][4];22 queue
        
          q;23 priority_queue
         
          
           ,greater
           
             > q2;24 25 bool operator < (Node a,Node b){ return a.x
            
             dis[p.x][p.y][p.s][xx][yy]+dis2[p.x][p.y][p.s]+1){62 dis2[xx][yy][i^1]=dis[p.x][p.y][p.s][xx][yy]+dis2[p.x][p.y][p.s]+1;63 q2.push(make_pair(dis2[xx][yy][i^1],Node(xx,yy,i^1)));64 }65 }66 }flag2[p.x][p.y][p.s]=1;67 }int re=-1;68 for(int i=0;i<=3;i++){69 if(dis2[tx][ty][i]==-1) continue;70 if(re==-1) re=dis2[tx][ty][i];71 else re=min(re,dis2[tx][ty][i]);72 }return re;73 }74 75 int main(){76 int i,j,k;77 N=rd(),M=rd();Q=rd();78 for(i=1;i<=N;i++){79 for(j=1;j<=M;j++) can[i][j]=rd();80 }81 memset(dis,-1,sizeof(dis));82 for(i=1;i<=N;i++){83 for(j=1;j<=M;j++){84 if(!can[i][j]) continue;can[i][j]=0;85 for(k=0;k<=3;k++){86 int ii=i+step[k][0],jj=j+step[k][1];87 if(can[ii][jj]) bfs1(i,j,k,ii,jj);88 }can[i][j]=1;89 }90 }91 for(i=1;i<=Q;i++){92 int x1=rd(),x2=rd(),x3=rd(),x4=rd(),x5=rd(),x6=rd();93 printf("%d\n",dijkstra(x1,x2,x3,x4,x5,x6));94 }95 return 0;96 }