Description
小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：
1.在一个 n*m 棋盘上有 n*m 个格子，其中有且只有一个格子是空白的，其余 n*m-1个格子上每个格子上有一个棋子，每个棋子的大小都是 1*1 的；
2.有些棋子是固定的，有些棋子则是可以移动的；
3.任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘，游戏可以玩 q 次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候，空白的格子在第EXi行EYi列，指定的可移动棋子的初始位置为第SXi行第SYi 列，目标位置为第TXi 行第TYi列。
假设小 B 每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。
Input
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n、m 和 q；
接下来的 n 行描述一个 n*m 的棋盘，每行有 m 个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，0 表示该格子上的棋子是固定的，1 表示该格子上的棋子可以移动或者该格子是空白的。
接下来的 q 行，每行包含 6 个整数依次是EXi、EYi、SXi、SYi、TXi、TYi，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。
Output
输出有 q 行，每行包含 1 个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出−1。
Sample Input
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
Sample Output
2
-1
讲道理，这题的预处理真的不是来恶心人的吗TAT
然后有一个小技巧：用1代表上，2代表左，3代表右，4代表下，则a的反方向就是5-a。
存一存代码。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,k,ex,ey,sx,sy,tx,ty,ans;
int map[][],deep[][],dis[][][],mov[][][][];
bool d[][],in[][][];
struct node{int x,y,k;}t1,t2;
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
node move(node t,int k)
{
if(k==)t.x--;if(k==)t.y--;
if(k==)t.y++;if(k==)t.x++;
return t;
}
int bfs(node s,node t)
{
node now,to;
memset(deep,0x3f,sizeof(deep));
memset(d,,sizeof(d));
queue<node>q;q.push(s);
deep[s.x][s.y]=;d[s.x][s.y]=true;
while(!q.empty()&&!d[t.x][t.y])
{
now=q.front();q.pop();
for(int k=;k<=;k++)
{
to=move(now,k);
if(!d[to.x][to.y]&&map[to.x][to.y]==)
{
d[to.x][to.y]=true;q.push(to);
deep[to.x][to.y]=deep[now.x][now.y]+;
}
}
}
return deep[t.x][t.y];
}
void init()
{
memset(mov,0x3f,sizeof(mov));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(map[i][j]==)continue;
map[i][j]=;
for(int k=;k<=;k++)
for(int l=;l<=;l++)
{
if(l<k){mov[i][j][k][l]=mov[i][j][l][k];continue;}
t1=move((node){i,j,k},k);t2=move((node){i,j,l},l);
if(map[t1.x][t1.y]==||map[t2.x][t2.y]==)continue;
mov[i][j][k][l]=bfs(t1,t2)+;
}
map[i][j]=;
}
}
void spfa(node s,node t)
{
ans=inf;
if(s.x==t.x&&s.y==t.y){ans=;return;}
if(map[s.x][s.y]==||map[t.x][t.y]==)return;
node now,to;
memset(dis,0x3f,sizeof(dis));
memset(in,,sizeof(in));
queue<node>q;
map[s.x][s.y]=;
for(int i=;i<=;i++)
{
q.push((node){s.x,s.y,i});
in[s.x][s.y][i]=true;
dis[s.x][s.y][i]=bfs((node){ex,ey,},move(s,i));
}
map[s.x][s.y]=;
while(!q.empty())
{
now=q.front();q.pop();
in[now.x][now.y][now.k]=false;
for(int i=;i<=;i++)
{
to=move(now,i);to.k=-i;
if(dis[now.x][now.y][now.k]+mov[now.x][now.y][now.k][i]<dis[to.x][to.y][-i])
{
dis[to.x][to.y][-i]=dis[now.x][now.y][now.k]+mov[now.x][now.y][now.k][i];
if(!in[to.x][to.y][to.k])q.push(to),in[to.x][to.y][to.k]=true;
}
}
}
for(int i=;i<=;i++)ans=min(ans,dis[t.x][t.y][i]);
}
int main()
{
n=read();m=read();k=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
map[i][j]=read();
init();
for(int i=;i<=k;i++)
{
ex=read();ey=read();sx=read();sy=read();tx=read();ty=read();
spfa((node){sx,sy,},(node){tx,ty,});
if(ans==inf)printf("-1\n");
else printf("%d\n",ans);
}
return ;
}