/*双向bfs （得分和单项的一样多....）70*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 35
#define maxm 810010
using namespace std;
int n,m,q,g[maxn][maxn];
int X,Y,sx,sy,ex,ey,falg,vis[maxn][maxn];
int xx[]={,,,-};
int yy[]={,-,,};
int f[maxn][maxn][maxn][maxn],s[maxn][maxn][maxn][maxn];
struct node
{
int kx,ky,xi,yi;
node (int xxx, int yyy, int tt, int ss):kx(xxx), ky(yyy), xi(tt), yi(ss){};
};
queue<node>Q;
void Bfs()
{
if(sx==ex&&sy==ey)
{
printf("0\n");
falg=;return;
}
while(!Q.empty())Q.pop();
f[X][Y][sx][sy]=;
s[X][Y][sx][sy]=;
Q.push(node(X,Y,sx,sy));
for(int i=;i<;i++)
{
int nx=xx[i]+ex;
int ny=yy[i]+ey;
if(nx>&&nx<=n&&ny>&&ny<=m&&g[nx][ny]&&f[nx][ny][ex][ey]==)
{
f[nx][ny][ex][ey]=;
s[nx][ny][ex][ey]=;
Q.push(node(nx,ny,ex,ey));
}
}
while(!Q.empty())
{
node t=Q.front();Q.pop();
int x=t.kx,y=t.ky;
int xs=t.xi,ys=t.yi;
int T=f[x][y][xs][ys];
int k=s[x][y][xs][ys];
for(int i=;i<;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
xs=t.xi;ys=t.yi;
if(nx>&&nx<=n&&ny>&&ny<=m&&g[nx][ny])
{
if(nx==xs&&ny==ys)xs=x,ys=y;
if(f[nx][ny][xs][ys]==)
{
f[nx][ny][xs][ys]=T;
s[nx][ny][xs][ys]=k+;
Q.push(node(nx,ny,xs,ys));
}
else if(f[nx][ny][xs][ys]!=T)
{
printf("%d\n",s[nx][ny][xs][ys]+k+);
falg=;return;
}
} }
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&g[i][j]);
while(q--)
{
scanf("%d%d%d%d%d%d",&X,&Y,&sx,&sy,&ex,&ey);
falg=;memset(f,,sizeof(f));Bfs();
if(falg==)printf("-1\n");
}
return ;
}
/*
后来看了别人的思路 机智啊！
本来bfs不超时的 nm*nm 但是加上q次询问就T了
问题就在这 我们重复的bfs太多了 能不能一次预处理好呢
但是考虑到每次的起点终点还有空格位置是在变化的
所以我们要与处理一些与这些无关的 但是对答案还有贡献的
考虑到目标棋子的移动必须先让空格移动到4周
所以我们把每个空格和目标棋子的相邻的组合作为状态
也就是有n*m*4个状态 每个状态不是相邻的 互相转移需要一定的步数
这个步数就使我们要预处理的东西
然后把每个状态映射成一个图 将目标棋盘转化成同样的状态 然后跑最短路
具体的细节看代码把
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 35
#define maxm 810010
using namespace std;
int n,m,q,g[maxn][maxn],num,head[maxm],kx,ky,sx,sy,ex,ey;
int f[maxn][maxn],dis[maxm],vis[maxm],ans;
struct node{int u,v,t,pre;}e[maxm];
int xx[]={-,,,};//上下左右 和下面的对应
int yy[]={,,-,};
void Init()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&g[i][j]);
}
void Add(int from,int to,int dis)
{
num++;e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void Bfs(int X,int Y,int xi,int yi,int k)
{
queue<int>qx,qy;
while(!qx.empty())qx.pop();
while(!qy.empty())qy.pop();
memset(f,,sizeof(f));
qx.push(xi);qy.push(yi);
f[xi][yi]=;//判重+步数记录
while(!qx.empty())
{
int x=qx.front();qx.pop();
int y=qy.front();qy.pop();
for(int i=;i<;i++)
{
int nx=x+xx[i];
int ny=y+yy[i];
if(nx==X&&ny==Y)continue;
if(nx>&&nx<=m&&ny>&&ny<=m&&g[nx][ny]&&f[nx][ny]==)
{
qx.push(nx);qy.push(ny);
f[nx][ny]=f[x][y]+;
}
}
}
if(k==)return;
for(int i=;i<;i++)
{
int nx=X+xx[i],ny=Y+yy[i];
if(f[nx][ny]==||(nx==xi&&ny==yi))continue;
Add(X**+Y*+k,X**+Y*+i,f[nx][ny]-);//一一映射
}
Add(X**+Y*+k,xi**+yi*+(k^),);//每组之间的状态连起来 这里的^ 就是左变变 上变下
}
void Ready()
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{ if(!g[i][j]) continue;
if(g[i-][j]) Bfs(i,j,i-,j,);
if(g[i+][j]) Bfs(i,j,i+,j,);
if(g[i][j-]) Bfs(i,j,i,j-,);
if(g[i][j+]) Bfs(i,j,i,j+,);
}
}
void SPFA()
{
queue<int>q;memset(dis,/,sizeof(dis));
for(int i=;i<;i++)
{
int nx=sx+xx[i];
int ny=sy+yy[i];
if(nx>&&nx<=n&&ny>&&ny<=m&&g[nx][ny]&&f[nx][ny])
{
int k=sx**+sy*+i;
q.push(k);vis[k]=;dis[k]=f[nx][ny]-;//转化成可表示的状态
}
}
while(!q.empty())
{
int k=q.front();q.pop();vis[k]=;
for(int i=head[k];i;i=e[i].pre)
if(dis[e[i].v]>dis[k]+e[i].t)
{
dis[e[i].v]=dis[k]+e[i].t;
if(vis[e[i].v]==)
{
vis[e[i].v]=;q.push(e[i].v);
}
}
}
}
int main()
{
Init();
Ready();
for(int i=;i<=q;i++)
{
scanf("%d%d%d%d%d%d",&kx,&ky,&sx,&sy,&ex,&ey);
if(sx==ex&&sy==ey)
{
printf("0\n");continue;
}
Bfs(sx,sy,kx,ky,);//把空格移到目标棋子附近
SPFA();ans=dis[];
for(int i=;i<;i++)
{
int k=ex**+ey*+i;
ans=min(ans,dis[k]);
}
if(ans==dis[])printf("-1\n");
else printf("%d\n",ans);
}
return ;
}