题目：https://www.luogu.org/problemnew/show/P1979
感到无从下手。但不妨用dp的角度来看。因为空格只有在指定棋子的旁边才有用，所以状态记成制定棋子的位置与空格在自己的哪侧。
转移有两种：与空格交换位置 或 让空格换一个方向。为了第二个转移，需要预处理，bfs出指定棋子在 (x,y) 时从它的哪边走到哪边的最短路。
dp的转移可以套到最短路里做。一开始需要让空格来到指定棋子的四个方向(bfs)。然后多源最短路或者做4遍最短路。
别忘了优先队列自然的就是从大到小排列的！！！
自己的写法需要特判走0步的情况。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=35,K=5,M=N*N,INF=0x3f3f3f3f-100; int n,m,Q,f[N][N][K][K],dis[N][N],dp[N][N][K]; int he,tl,xx[K]={-1,0,0,1},yy[K]={0,-1,1,0}; int ex,ey,sx,sy,Tx,Ty,ans,tmp; bool b[N][N],vis[N][N][K]; struct Node{ int x,y,p,dis; Node(int x=0,int y=0,int a=0,int d=0):x(x),y(y),p(a),dis(d) {} bool operator< (const Node &b) const {return dis>b.dis;}//>!!! }q[M]; priority_queue<Node> qu; void bfs(int x1,int y1,int x2,int y2) { he=tl=0; int tx,ty; q[++tl]=Node(x1,y1,0,0); memset(dis,0x3f,sizeof dis); dis[x1][y1]=0; while(he<tl) { Node k=q[++he]; for(int i=0;i<=3;i++) { tx=k.x+xx[i]; ty=k.y+yy[i]; if(!b[tx][ty])continue; if(dis[tx][ty]>INF) { dis[tx][ty]=dis[k.x][k.y]+1; q[++tl]=Node(tx,ty,0,0); if(tx==x2&&ty==y2)return; } } } } void init() { memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(b[i][j]) for(int p0=0;p0<=3;p0++) for(int p1=p0+1,x1,y1,x2,y2;p1<=3;p1++) { x1=i+xx[p0]; y1=j+yy[p0]; x2=i+xx[p1]; y2=j+yy[p1]; if(!b[x1][y1]||!b[x2][y2]) continue; b[i][j]=0; bfs(x1,y1,x2,y2); f[i][j][p0][p1]=f[i][j][p1][p0] =dis[x2][y2]; b[i][j]=1; } } void solve(int yp) { while(qu.size())qu.pop(); qu.push(Node(sx,sy,yp,0)); memset(dp,0x3f,sizeof dp); dp[sx][sy][yp]=0;// memset(vis,0,sizeof vis); while(qu.size()) { Node k=qu.top(); qu.pop(); if(vis[k.x][k.y][k.p])continue; vis[k.x][k.y][k.p]=1; if(k.x==Tx&&k.y==Ty)return; int tp=3-k.p,tx=k.x+xx[k.p],ty=k.y+yy[k.p]; if(dp[tx][ty][tp]>dp[k.x][k.y][k.p]+1) { dp[tx][ty][tp]=dp[k.x][k.y][k.p]+1; qu.push(Node(tx,ty,tp,dp[tx][ty][tp])); } tx=k.x; ty=k.y; tp=k.p; for(int i=0;i<=3;i++) { if(i==tp)continue; if(f[tx][ty][tp][i]<INF&& dp[tx][ty][i]>dp[tx][ty][tp]+f[tx][ty][tp][i]) { dp[tx][ty][i]=dp[tx][ty][tp]+f[tx][ty][tp][i]; qu.push(Node(tx,ty,i,dp[tx][ty][i])); } } } } int main() { scanf("%d%d%d",&n,&m,&Q); for(int i=1;i<=n;i++) for(int j=1,d;j<=m;j++) scanf("%d",&d),b[i][j]=d; init(); he=tl=0; while(Q--) { scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&Tx,&Ty); if(sx==Tx&&sy==Ty) { printf("0 "); continue; } ans=INF+5; for(int i=0,tx,ty;i<=3;i++) { tx=sx+xx[i]; ty=sy+yy[i]; if(!b[tx][ty])continue; b[sx][sy]=0; bfs(ex,ey,tx,ty); b[sx][sy]=1; tmp=dis[tx][ty]; if(tmp>INF)continue; solve(i); ans=min(ans,tmp+min(min(dp[Tx][Ty][0],dp[Tx][Ty][1]), min(dp[Tx][Ty][2],dp[Tx][Ty][3]))); } printf("%d ",ans>INF?-1:ans); } return 0; }