测试地址：华容道
做法：简单的BFS是肯定过不了的，我们来分析一下时间都花在了哪里：在多个询问中，有许多状态被重复搜索了，使得时间被拖慢。我们可以发现，在许多的状态中，只有空格挨在要移的棋子旁边的状态才是有用的，于是我们用A[i][j][h]表示要移的棋子在(i,j)且空格在h方向上紧挨棋子的状态，用move[i][j][k][h]表示棋子在(i,j)，空格在k方向上紧挨棋子，要将棋子向h方向移动一格的最少步数，即从A[i][j][k]到A[i'][j'][h‘]的最少步数，其中(i',j')为棋子向h方向移动后的坐标，h'为h的反方向（可用BFS求出）。然后我们发现，状态间的转移其实就相当于连边（有向），不同的状态就是点，例如A[i][j][k]和A[i'][j'][h']间连边的边权是move[i][j][k][h]，所以对于每个询问，我们首先BFS求出将空格移到起始位置，然后用SPFA求出最短路径即可。
以下是本人代码（洛谷100，Vijos70，求大神告知原因）：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 999999999
using namespace std;
int n,m,p,mp[31][31],d[4][2]={{1,0},{-1,0},{0,1},{0,-1}},st=0,a[31][31][4],first[10010]={0};
int last[31][31]={0},tot=0,inx=0,l,r;
int dist[10010],Q[10010];
bool vis[10010]={0};
struct
{
int v,d,next;
}e[100010];
struct
{
int x,y;
}q[100010];
void insert(int x,int y,int d)
{
e[++tot].v=y;
e[tot].d=d;
e[tot].next=first[x];
first[x]=tot;
}
void input()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&mp[i][j]);
for(int k=0;k<=3;k++) a[i][j][k]=++st;
}
}
bool bfs(int L,int R,int tx,int ty)
{
for(int i=L;i<=R;i++)
for(int j=0;j<=3;j++)
if (mp[q[i].x+d[j][0]][q[i].y+d[j][1]])
{
q[++r].x=q[i].x+d[j][0];
q[r].y=q[i].y+d[j][1];
if (last[q[r].x][q[r].y]==inx) r--;
else last[q[r].x][q[r].y]=inx;
if (q[r].x==tx&&q[r].y==ty) return 1;
}
l=R;return 0;
}
int find(int sx,int sy,int tx,int ty)
{
if (sx==tx&&sy==ty) return 0;
int step=1,x=tot;
q[1].x=sx,q[1].y=sy;inx++;
l=0,r=1;
bool flag;
while(l<r&&(flag=!bfs(l+1,r,tx,ty))) step++;
tot=x;
if (flag) return inf;
else return step;
}
void prepare()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (mp[i][j])
{
for(int k=0;k<=3;k++)
if (mp[i+d[k][0]][j+d[k][1]])
{
insert(a[i][j][k],a[i+d[k][0]][j+d[k][1]][k^1],1);
for(int h=0;h<=3;h++)
if (k!=h&&mp[i+d[h][0]][j+d[h][1]])
{
mp[i][j]=0;
int move=find(i+d[k][0],j+d[k][1],i+d[h][0],j+d[h][1])+1;
if (move<inf) insert(a[i][j][k],a[i+d[h][0]][j+d[h][1]][h^1],move);
mp[i][j]=1;
}
}
}
}
int spfa(int S,int T)
{
memset(vis,0,sizeof(vis));
int h=0,t=1,x;
Q[1]=S;
for(int i=1;i<=10009;i++) dist[i]=inf;
dist[S]=0;
while(h!=t)
{
x=Q[h=((h%10000)+1)];
vis[x]=0;
for(int i=first[x];i;i=e[i].next)
if (dist[e[i].v]>dist[x]+e[i].d)
{
dist[e[i].v]=dist[x]+e[i].d;
if (!vis[e[i].v]) {vis[e[i].v]=1;Q[t=((t%10000)+1)]=e[i].v;}
}
}
if (dist[T]<inf) return dist[T];
else return -1;
}
void work()
{
int ex,ey,sx,sy,tx,ty;
for(int i=1;i<=p;i++)
{
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if (sx==tx&&sy==ty) {printf("0
");continue;}
if (!mp[sx][sy]||!mp[tx][ty]) {printf("-1
");continue;}
int S=++st,T=++st;
mp[sx][sy]=0;
for(int j=0;j<=3;j++)
{
int move=find(ex,ey,sx+d[j][0],sy+d[j][1]);
if (move<inf) insert(S,a[sx][sy][j],move);
}
mp[sx][sy]=1;
for(int j=0;j<=3;j++)
if (mp[tx+d[j][0]][ty+d[j][1]]) insert(a[tx][ty][j],T,0);
printf("%d
",spfa(S,T));
}
}
int main()
{
input();
prepare();
work();
return 0;
}