1 #include<set>
  2 #include<map>
  3 #include<queue>
  4 #include<stack>
  5 #include<ctime>
  6 #include<cmath>
  7 #include<string>
  8 #include<vector>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<cstring>
 12 #include<iostream>
 13 #include<algorithm>
 14 using namespace std;
 15 int mov[32][32][5][5];
 16 int dn[5]={0,-1,1,0,0},dm[5]={0,0,0,-1,1},id[32][32][5];
 17 bool mp[32][32],bj[32][32];
 18 struct data{
 19   int x,y,step;
 20 }q[1000000];
 21 struct node{
 22   int nex,to,w;
 23 }e[1000000];
 24 int head1[100000],edge=0,dis[1000000],vis[1000000];
 25 void add(int from,int to,int w){
 26   e[++edge].nex=head1[from];
 27   e[edge].to=to;
 28   e[edge].w=w;
 29   head1[from]=edge;
 30 }
 31 queue<int>Q;
 32 void SPFA(){
 33   int ex,ey,sx,sy,tx,ty;
 34   scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
 35   if(sx==tx && sy==ty) {printf("0\n");return;}
 36   memset(dis,127/3,sizeof(dis));
 37   int head=0,tail=1;
 38   q[tail].x=ex,q[tail].y=ey;q[tail].step=0;
 39   memset(bj,0,sizeof(bj));
 40   bj[ex][ey]=1;
 41   while(head<tail){
 42     ++head;
 43     for(int i=1;i<=4;i++){
 44       int xx=q[head].x+dn[i],yy=q[head].y+dm[i];
 45       if(bj[xx][yy]) continue;
 46       if(!mp[xx][yy])continue;
 47       if(xx==sx && yy==sy){
 48     if(i==1)
 49       dis[id[sx][sy][2]]=min(dis[id[sx][sy][2]],q[head].step);
 50     if(i==2)
 51       dis[id[sx][sy][1]]=min(dis[id[sx][sy][1]],q[head].step);
 52     if(i==3)
 53       dis[id[sx][sy][4]]=min(dis[id[sx][sy][4]],q[head].step);
 54     if(i==4)
 55       dis[id[sx][sy][3]]=min(dis[id[sx][sy][3]],q[head].step);
 56     continue;
 57       }
 58       bj[xx][yy]=1;
 59       ++tail;
 60       q[tail].x=xx,q[tail].y=yy,q[tail].step=q[head].step+1;
 61     }
 62   }
 63   Q.push(id[sx][sy][2]),vis[id[sx][sy][2]]=1;
 64   Q.push(id[sx][sy][1]),vis[id[sx][sy][1]]=1;
 65   Q.push(id[sx][sy][3]),vis[id[sx][sy][3]]=1;
 66   Q.push(id[sx][sy][4]),vis[id[sx][sy][4]]=1;
 67   while(!Q.empty()){
 68     int u=Q.front();
 69     vis[u]=0;
 70     Q.pop();
 71     for(int i=head1[u];i;i=e[i].nex){
 72       int v=e[i].to;
 73       if(dis[v]>dis[u]+e[i].w){
 74     dis[v]=dis[u]+e[i].w;
 75     if(!vis[v]) Q.push(v),vis[v]=1;
 76       }
 77     }
 78   }
 79   int l1=dis[id[tx][ty][1]],l2=dis[id[tx][ty][2]],l3=dis[id[tx][ty][3]],l4=dis[id[tx][ty][4]];
 80   int zx=min(min(l1,l2),min(l3,l4));
 81   if(zx==dis[0]) printf("-1\n");
 82   else printf("%d\n",zx);
 83 }
 84 int main()
 85 {
 86   freopen("!.in","r",stdin);
 87   freopen("!.out","w",stdout);
 88   int n,m,qes;
 89   scanf("%d%d%d",&n,&m,&qes);
 90   memset(mov,127/3,sizeof(mov));
 91   int tot=0;
 92   for(int i=1;i<=n;i++)
 93     for(int j=1;j<=m;j++){
 94       scanf("%d",&mp[i][j]);
 95       if(mp[i][j]) id[i][j][1]=++tot,id[i][j][2]=++tot,id[i][j][3]=++tot,id[i][j][4]=++tot;
 96     }
 97   for(int i=1;i<=n;i++)
 98     for(int j=1;j<=m;j++){
 99       if(!mp[i][j]) continue;
100       for(int k1=1;k1<=4;k1++) 
101     for(int k2=1;k2<=4;k2++){
102       int kx=i+dn[k1],ky=j+dm[k1];
103       int nx=i+dn[k2],ny=j+dm[k2];
104       if(!mp[kx][ky] || !mp[nx][ny]) continue;
105       int head=0,tail=1;
106       q[tail].x=kx,q[tail].y=ky;
107       if(kx==nx && ky==ny){mov[i][j][k1][k2]=1;continue;}
108       memset(bj,0,sizeof(bj));
109       bj[kx][ky]=1;
110       while(head<tail){
111         head++;
112         for(int p=1;p<=4;p++){
113           int xx=q[head].x+dn[p],yy=q[head].y+dm[p];
114           if(bj[xx][yy]) continue;
115           if(!mp[xx][yy]) continue;
116           if(xx==i && yy==j) continue;
117           bj[xx][yy]=1;
118           tail++;
119           q[tail].x=xx,q[tail].y=yy,q[tail].step=q[head].step+1;
120           if(xx==nx && yy==ny){mov[i][j][k1][k2]=q[tail].step+1;break;}
121         }
122       }
123     }
124     }
125   for(int i=1;i<=n;i++)
126     for(int j=1;j<=m;j++){
127       if(!mp[i][j]) continue;
128       for(int k=1;k<=4;k++){
129     int kx=i+dn[k],ky=j+dm[k];
130     if(!mp[kx][ky]) continue;
131     for(int k1=1;k1<=4;k1++){
132       int nx=i+dn[k1],ny=j+dm[k1];
133       if(!mp[nx][ny]) continue;
134       if(k1==1)
135         add(id[i][j][k],id[nx][ny][2],mov[i][j][k][k1]);
136       if(k1==2)
137         add(id[i][j][k],id[nx][ny][1],mov[i][j][k][k1]);
138       if(k1==3)
139         add(id[i][j][k],id[nx][ny][4],mov[i][j][k][k1]);
140       if(k1==4)
141         add(id[i][j][k],id[nx][ny][3],mov[i][j][k][k1]);
142     }
143       }
144     }
145   for(int i=1;i<=qes;i++)
146     SPFA();
147   return 0;
148 }
149