时间限制：1 s 内存限制：128 MB
题解
考场上完全是按照暴搜来做的，但是打得大概不是很优美，连暴搜的分数都没拿全。题解倒是给的非常详细，但是看了很多遍都不知道应该怎么实现。最后决定一个函数一个函数地堆，堆了好多节课才堆完。唯一可取的地方大概是没有参考标程，完全是自己实现的，调过之后很有成就感。所以说即使是很困难的事，也还是有办法做到的啊。
棋盘毕竟小，除了暴搜之外其他看起来暴力的方法还是可以尝试的。华容道游戏可以分成两部分，第一部分是空白格移动到起始格周围，第二部分是空白格给起始棋子铺路直到抵达目标格。把每一个棋子上方规定为0，左方为1，右方为2，下方为3。在执行第二部分时空白格始终在目标格周围，所以我们需要掌握的其实是空白格从每一个格子0到1、1到3、3到2一类绕圈的步数，而且这个最短距离不能经过围绕的那一点，这个过程相当于建图。棋盘是固定的，所以整个程序对第二部分只需要一次BFS，第一部分则需要对每一个数据BFS。拥有了这两个距离，我们就可以每次用一遍带方向转移的spfa求出到目标点的最短路，不可达则输出-1。spfa过程中有两种转移：一是把白格子与起始棋子交换位置，花费1；二是把白格子从当前棋子的一侧移到另一侧，花费第二部分预处理出的路径长。数据里有一个坑就是起始点和目标点重合，这样的数据还莫名多……要是在考场上多半会考虑到这种情况，但是自己练习就不会注意到，还是态度不一样时间不一样的问题，不会为了拿分考虑每一个细节。
自己打完这道题之后成就感很高，如果看了标程也多半是过了就过了没有什么感觉。我们常常花很多时间去做那些无关紧要，也并不能提升自己的事，为了逃避困难，为了当下的轻松。但是事情过去之后，还是自己走过的经历更能带来美好的回忆。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int sj=32; struct point { int x,y,dir,step; }temp; queue<point> q; int n,m,ca,ex,ey,sx,sy,tx,ty,ans,tp,bx; int dis[sj][sj][4],f[sj][sj][4][4],jg[4],st[sj][sj]; bool kd[sj][sj],r[sj][sj][4],jl[sj][sj]; void bfs1(int x,int y) { if(kd[x-1][y]){ memset(jl,0,sizeof(jl)); temp.x=x-1,temp.y=y,temp.step=0; while(!q.empty()) q.pop(); q.push(temp); jl[x-1][y]=jl[x][y]=1; while(!q.empty()){ temp=q.front(),q.pop(); if(temp.x==x+1&&temp.y==y) f[x][y][0][3]=f[x][y][3][0]=temp.step; if(temp.x==x&&temp.y==y+1) f[x][y][0][2]=f[x][y][2][0]=temp.step; if(temp.x==x&&temp.y==y-1) f[x][y][0][1]=f[x][y][1][0]=temp.step; if(kd[temp.x+1][temp.y]&&!jl[temp.x+1][temp.y]){ q.push((point){temp.x+1,temp.y,temp.dir,temp.step+1}); jl[temp.x+1][temp.y]=1; } if(kd[temp.x-1][temp.y]&&!jl[temp.x-1][temp.y]){ q.push((point){temp.x-1,temp.y,temp.dir,temp.step+1}); jl[temp.x-1][temp.y]=1; } if(kd[temp.x][temp.y+1]&&!jl[temp.x][temp.y+1]){ q.push((point){temp.x,temp.y+1,temp.dir,temp.step+1}); jl[temp.x][temp.y+1]=1; } if(kd[temp.x][temp.y-1]&&!jl[temp.x][temp.y-1]){ q.push((point){temp.x,temp.y-1,temp.dir,temp.step+1}); jl[temp.x][temp.y-1]=1; } } } if(kd[x][y-1]){ memset(jl,0,sizeof(jl)); temp.x=x,temp.y=y-1,temp.step=0; while(!q.empty()) q.pop(); q.push(temp); jl[x][y-1]=jl[x][y]=1; while(!q.empty()){ temp=q.front(),q.pop(); if(temp.x==x+1&&temp.y==y) f[x][y][1][3]=f[x][y][3][1]=temp.step; if(temp.x==x&&temp.y==y+1) f[x][y][1][2]=f[x][y][2][1]=temp.step; if(kd[temp.x+1][temp.y]&&!jl[temp.x+1][temp.y]){ q.push((point){temp.x+1,temp.y,temp.dir,temp.step+1}); jl[temp.x+1][temp.y]=1; } if(kd[temp.x-1][temp.y]&&!jl[temp.x-1][temp.y]){ q.push((point){temp.x-1,temp.y,temp.dir,temp.step+1}); jl[temp.x-1][temp.y]=1; } if(kd[temp.x][temp.y+1]&&!jl[temp.x][temp.y+1]){ q.push((point){temp.x,temp.y+1,temp.dir,temp.step+1}); jl[temp.x][temp.y+1]=1; } if(kd[temp.x][temp.y-1]&&!jl[temp.x][temp.y-1]){ q.push((point){temp.x,temp.y-1,temp.dir,temp.step+1}); jl[temp.x][temp.y-1]=1; } } } if(kd[x][y+1]){ memset(jl,0,sizeof(jl)); temp.x=x,temp.y=y+1,temp.step=0; while(!q.empty()) q.pop(); q.push(temp); jl[x][y+1]=jl[x][y]=1; while(!q.empty()){ temp=q.front(),q.pop(); if(temp.x==x+1&&temp.y==y){ f[x][y][2][3]=f[x][y][3][2]=temp.step; break; } if(kd[temp.x+1][temp.y]&&!jl[temp.x+1][temp.y]){ q.push((point){temp.x+1,temp.y,temp.dir,temp.step+1}); jl[temp.x+1][temp.y]=1; } if(kd[temp.x-1][temp.y]&&!jl[temp.x-1][temp.y]){ q.push((point){temp.x-1,temp.y,temp.dir,temp.step+1}); jl[temp.x-1][temp.y]=1; } if(kd[temp.x][temp.y+1]&&!jl[temp.x][temp.y+1]){ q.push((point){temp.x,temp.y+1,temp.dir,temp.step+1}); jl[temp.x][temp.y+1]=1; } if(kd[temp.x][temp.y-1]&&!jl[temp.x][temp.y-1]){ q.push((point){temp.x,temp.y-1,temp.dir,temp.step+1}); jl[temp.x][temp.y-1]=1; } } } } void bfs2() { memset(st,0x3f,sizeof(st)); bx=st[0][0]; while(!q.empty()) q.pop(); q.push((point){ex,ey,0,0}); st[ex][ey]=0; kd[sx][sy]=0; while(!q.empty()){ temp=q.front(); if(st[temp.x][temp.y]<temp.step){ q.pop(); continue; } q.pop(); if(kd[temp.x+1][temp.y]&&temp.step+1<st[temp.x+1][temp.y]){ q.push((point){temp.x+1,temp.y,0,temp.step+1}); st[temp.x+1][temp.y]=temp.step+1; } if(kd[temp.x-1][temp.y]&&temp.step+1<st[temp.x-1][temp.y]){ q.push((point){temp.x-1,temp.y,0,temp.step+1}); st[temp.x-1][temp.y]=temp.step+1; } if(kd[temp.x][temp.y+1]&&temp.step+1<st[temp.x][temp.y+1]){ q.push((point){temp.x,temp.y+1,0,temp.step+1}); st[temp.x][temp.y+1]=temp.step+1; } if(kd[temp.x][temp.y-1]&&temp.step+1<st[temp.x][temp.y-1]){ q.push((point){temp.x,temp.y-1,0,temp.step+1}); st[temp.x][temp.y-1]=temp.step+1; } } jg[0]=st[sx-1][sy]; jg[1]=st[sx][sy-1]; jg[2]=st[sx][sy+1]; jg[3]=st[sx+1][sy]; kd[sx][sy]=1; } void spfa() { memset(dis,0x3f,sizeof(dis)); tp=dis[0][0][0]; for(int i=0;i<=3;i++) if(jg[i]!=bx) dis[sx][sy][i]=jg[i]; while(!q.empty()) q.pop(); for(int i=0;i<=3;i++) if(jg[i]!=bx) q.push((point){sx,sy,i,jg[i]}),r[sx][sy][i]=1; int nx,ny,ns,nd; while(!q.empty()){ nx=q.front().x,ny=q.front().y,ns=dis[q.front().x][q.front().y][q.front().dir],nd=q.front().dir; q.pop(),r[nx][ny][nd]=0; if(nd==0){ if(kd[nx-1][ny]&&dis[nx-1][ny][3]>ns+1){ dis[nx-1][ny][3]=ns+1; if(!r[nx-1][ny][3]) q.push((point){nx-1,ny,3,ns+1}); } if(dis[nx][ny][1]>ns+f[nx][ny][0][1]){ dis[nx][ny][1]=ns+f[nx][ny][0][1]; if(!r[nx][ny][1]) q.push((point){nx,ny,1,dis[nx][ny][1]}); } if(dis[nx][ny][2]>ns+f[nx][ny][0][2]){ dis[nx][ny][2]=ns+f[nx][ny][0][2]; if(!r[nx][ny][2]) q.push((point){nx,ny,2,dis[nx][ny][2]}); } if(dis[nx][ny][3]>ns+f[nx][ny][0][3]){ dis[nx][ny][3]=ns+f[nx][ny][0][3]; if(!r[nx][ny][3]) q.push((point){nx,ny,3,dis[nx][ny][3]}); } } if(nd==1){ if(kd[nx][ny-1]&&dis[nx][ny-1][2]>ns+1){ dis[nx][ny-1][2]=ns+1; if(!r[nx][ny-1][2]) q.push((point){nx,ny-1,2,ns+1}); } if(dis[nx][ny][0]>ns+f[nx][ny][1][0]){ dis[nx][ny][0]=ns+f[nx][ny][1][0]; if(!r[nx][ny][0]) q.push((point){nx,ny,0,dis[nx][ny][0]}); } if(dis[nx][ny][2]>ns+f[nx][ny][1][2]){ dis[nx][ny][2]=ns+f[nx][ny][1][2]; if(!r[nx][ny][2]) q.push((point){nx,ny,2,dis[nx][ny][2]}); } if(dis[nx][ny][3]>ns+f[nx][ny][1][3]){ dis[nx][ny][3]=ns+f[nx][ny][1][3]; if(!r[nx][ny][3]) q.push((point){nx,ny,3,dis[nx][ny][3]}); } } if(nd==2){ if(kd[nx][ny+1]&&dis[nx][ny+1][1]>ns+1){ dis[nx][ny+1][1]=ns+1; if(!r[nx][ny+1][1]) q.push((point){nx,ny+1,1,ns+1}); } if(dis[nx][ny][1]>ns+f[nx][ny][2][1]){ dis[nx][ny][1]=ns+f[nx][ny][2][1]; if(!r[nx][ny][1]) q.push((point){nx,ny,1,dis[nx][ny][1]}); } if(dis[nx][ny][0]>ns+f[nx][ny][2][0]){ dis[nx][ny][0]=ns+f[nx][ny][2][0]; if(!r[nx][ny][0]) q.push((point){nx,ny,0,dis[nx][ny][0]}); } if(dis[nx][ny][3]>ns+f[nx][ny][2][3]){ dis[nx][ny][3]=ns+f[nx][ny][2][3]; if(!r[nx][ny][3]) q.push((point){nx,ny,3,dis[nx][ny][3]}); } } if(nd==3){ if(kd[nx+1][ny]&&dis[nx+1][ny][0]>ns+1){ dis[nx+1][ny][0]=ns+1; if(!r[nx+1][ny][0]) q.push((point){nx+1,ny,0,ns+1}); } if(dis[nx][ny][1]>ns+f[nx][ny][3][1]){ dis[nx][ny][1]=ns+f[nx][ny][3][1]; if(!r[nx][ny][1]) q.push((point){nx,ny,1,dis[nx][ny][1]}); } if(dis[nx][ny][2]>ns+f[nx][ny][3][2]){ dis[nx][ny][2]=ns+f[nx][ny][3][2]; if(!r[nx][ny][2]) q.push((point){nx,ny,2,dis[nx][ny][2]}); } if(dis[nx][ny][0]>ns+f[nx][ny][3][0]){ dis[nx][ny][0]=ns+f[nx][ny][3][0]; if(!r[nx][ny][0]) q.push((point){nx,ny,0,dis[nx][ny][0]}); } } } for(int i=0;i<=3;i++) if(ans>dis[tx][ty][i]) ans=dis[tx][ty][i]; } int main() { scanf("%d%d%d",&n,&m,&ca); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&kd[i][j]); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(kd[i][j]) bfs1(i,j); for(int l=1;l<=ca;l++){ scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty); if(tx==sx&&ty==sy){ printf("0 "); continue; } bfs2(); ans=0x7fffffff; spfa(); if(ans==tp) printf("-1 "); else printf("%d ",ans); } return 0; }