```cpp
/***********************
* Problem: *
* User: mzg1816_LRL *
* Language: C++ *
* Date：2019. *
* 算法：*
**********************/
#define ri register int
#define ll long long
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(register int i=(a);i>=(b);--i)
#define ee(i,a) for(register int i=head[a];i;i=e[i].nxt)
#include<bits/stdc++.h>
using namespace std;
const int N=35;
const int M=2055;
const int inf=0x3f3f3f3f;
char ss[1<<21],*A=ss,*B=ss,c;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<21,stdin),A==B)?EOF:*A++;}
/*struct RD{
template<class T>
RD&operator>>(T&x){
ri f=1;c=gc();x=0;while(c<48||c>57){if(c=='-')f=-1;c=gc();}
while(c>47&&c<58){x=(x<<3)+(x<<1)+(c^48);c=gc();}x*=f;
}
}rd;*/
template<class T>inline void rd(T&x){
ri f=1;c=gc();x=0;while(c<48||c>57){if(c=='-')f=-1;c=gc();}
while(c>47&&c<58){x=(x<<3)+(x<<1)+(c^48);c=gc();}x*=f;
}
struct ZB{
int x,y;
};
struct DIS{
int d,cx,cy,bx,by;
bool operator<(const DIS&rhs)const{
return d>rhs.d;
}
};
int n,m,q,mp[N][N],f[N][N][4][N][N],dis[N][N][N][N],vis[N][N],jishu[N][N],dis0[N][N][N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
priority_queue<DIS> qq;
void bfs(int x,int y,int d){
int sx=x+dx[d],sy=y+dy[d],hv=0,tg=0;
if(mp[sx][sy]==0)return;
mp[x][y]=0;
memset(jishu,0,sizeof(jishu));
rep(i,0,3){//目标点计数
if(i==d)continue;
int nx=x+dx[i];
int ny=y+dy[i];
if(mp[nx][ny]==0)continue;
jishu[nx][ny]=1;
tg++;
}
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
f[x][y][d][sx][sy]=0;
ZB sts;sts.x=sx;sts.y=sy;
queue<ZB> q;q.push(sts);
while(!q.empty()){
if(hv==tg)break;
ZB qu=q.front();q.pop();
rep(i,0,3){
int nx=qu.x+dx[i];
int ny=qu.y+dy[i];
if(mp[nx][ny]&&!vis[nx][ny]){
vis[nx][ny]=1;
f[x][y][d][nx][ny]=f[x][y][d][qu.x][qu.y]+1;
hv+=jishu[nx][ny];
ZB ns;ns.x=nx;ns.y=ny;q.push(ns);
}
}
}
mp[x][y]=1;
}
void bfs2(int x,int y,int sx,int sy){
//int sx=x+dx[d],sy=y+dy[d];
int hv=0,tg=0;
if(mp[sx][sy]==0)return;
mp[x][y]=0;
memset(jishu,0,sizeof(jishu));
rep(i,0,3){//目标点计数
//if(i==d)continue;
int nx=x+dx[i];
int ny=y+dy[i];
if(mp[nx][ny]==0)continue;
jishu[nx][ny]=1;
tg++;
}
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
dis0[sx][sy][sx][sy]=0;
ZB sts;sts.x=sx;sts.y=sy;
queue<ZB> q;q.push(sts);
while(!q.empty()){
if(hv==tg)break;
ZB qu=q.front();q.pop();
rep(i,0,3){
int nx=qu.x+dx[i];
int ny=qu.y+dy[i];
if(mp[nx][ny]&&!vis[nx][ny]){
vis[nx][ny]=1;
dis0[sx][sy][nx][ny]=dis0[sx][sy][qu.x][qu.y]+1;
hv+=jishu[nx][ny];
ZB ns;ns.x=nx;ns.y=ny;q.push(ns);
}
}
}
mp[x][y]=1;
}
int main()
{
freopen("read.txt","r",stdin);
//rd>>n>>m>>q;
rd(n),rd(m),rd(q);
rep(i,1,n){
rep(j,1,m){
//rd>>mp[i][j];
rd(mp[i][j]);
}
}
//处理出当曹操在i,j位置,空格从曹操上下左右（1,0,3,2）移动到曹操上下左右的最短路径
memset(f,0x3f,sizeof(f));
rep(i,1,n){
rep(j,1,m){
if(mp[i][j]==0)continue;
rep(d,0,3){
bfs(i,j,d);
}
}
}
//printf("f 1 3 2 1=%d\n",f[1][3][2][2]);
//处理每个询问，处理前先BFS出空格移动到曹操周围的步数
rep(sv,1,q){
int bx,by,sx,sy,ex,ey,x,y,ans=-1;
//rd>>bx>>by>>sx>>sy>>ex>>ey;
rd(bx),rd(by),rd(sx),rd(sy),rd(ex),rd(ey);
if(mp[sx][sy]==0||mp[ex][ey]==0){
puts("-1");
continue;
}
if(sx==ex&&sy==ey){
puts("0");
continue;
}
memset(dis0,0x3f,sizeof(dis0));
bfs2(sx,sy,bx,by);
// printf("dis0 3 2 2 2=%d\n",dis0[3][2][2][2]);
memset(dis,0x3f,sizeof(dis));
priority_queue<DIS> EMPTY;
swap(qq,EMPTY);
rep(d,0,3){
int nx=sx+dx[d];
int ny=sy+dy[d];
if(dis0[bx][by][nx][ny]<inf){
DIS sts;sts.d=dis0[bx][by][nx][ny];
sts.cx=sx;sts.cy=sy;sts.bx=nx;sts.by=ny;
dis[sx][sy][nx][ny]=dis0[bx][by][nx][ny];//dis(x,y,i,j)代表曹操在(x,y)空格在(i,j)的最少步数
qq.push(sts);
}
}
while(!qq.empty()){
DIS qu=qq.top();qq.pop();
x=qu.cx;y=qu.cy;
int kx=qu.bx,ky=qu.by;
if(x==ex&&y==ey){
//printf("%d\n",qu.d);
ans=qu.d;
break;
}
//空格与曹操交换位置
if(dis[x][y][kx][ky]+1<dis[kx][ky][x][y]){
dis[kx][ky][x][y]=dis[x][y][kx][ky]+1;
DIS ns;ns.cx=kx;ns.cy=ky;ns.bx=x;ns.by=y;
ns.d=dis[kx][ky][x][y];
qq.push(ns);
}
//空格改变在曹操附近的位置
int bs;
if(kx-x==-1&&ky-y==0)bs=1;
else if(kx-x==1&&ky-y==0)bs=0;
else if(kx-x==0&&ky-y==1)bs=2;
else if(kx-x==0&&ky-y==-1)bs=3;
rep(i,0,3){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx==kx&&ny==ky)continue;
if(mp[nx][ny]&&f[x][y][bs][nx][ny]<inf&&dis[x][y][kx][ky]+f[x][y][bs][nx][ny]<dis[x][y][nx][ny]){
dis[x][y][nx][ny]=dis[x][y][kx][ky]+f[x][y][bs][nx][ny];
DIS ns;ns.cx=x;ns.cy=y;ns.bx=nx;ns.by=ny;
ns.d=dis[x][y][nx][ny];
qq.push(ns);
}
}
}
printf("%d\n",ans);
}
return 0;
}
```
by LRL52 @ 2019-02-09 22:02:28
LOJ通过记录：https://loj.ac/problem/2613
by LRL52 @ 2019-02-09 22:04:06
LOJ通过记录:https://loj.ac/submission/331745
上面发错了
by LRL52 @ 2019-02-09 22:09:11
正常，卡常时交几次分都不一样
by Sai0511 @ 2019-02-09 22:12:08
@[Sai_0511](/space/show?uid=114320) 不正常啊，怎么一个点都不会超过500ms的，时限是1000ms，交上去过了的都不到500ms
by LRL52 @ 2019-02-09 22:16:51
好像卡常是有点严重
by LRL52 @ 2019-02-09 22:20:14
https://www.luogu.org/recordnew/show/16148196
终于卡过了
by LRL52 @ 2019-02-09 22:22:39
正常正常
by FP·荷兰猪 @ 2019-02-09 22:26:01
感觉某谷评测机慢了
by chenlingxi @ 2019-02-09 22:27:31
蒟蒻围观红名巨佬们 $\huge{ORZ}$
by teacup @ 2019-02-09 22:52:51