#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<queue> #include<map> #include<iostream> using namespace std; #define ll long long #define INF 0x3f3f3f3f #define N 35 int rd() { int f=1,s=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+(c^48);c=getchar();} return f*s; } const int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; //下上右左 int n,m,q; int mp[N][N]; int ex,ey,sx,sy,tx,ty; int cnt[N][N][5]; bool check(int xx,int yy) { if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]==0) return 0; return 1; } int tot; struct node{ int x,y,stp/*广搜的时候用 存步数*/; }; bool vis[N][N],mark[N*N]/*spfa的标记数组*/; vector<pair<int,int> >G[N*N]; void add(int u,int v,int w) { G[u].push_back(make_pair(v,w)); } int bfs(int ax,int ay,int bx,int by,int cx,int cy) {//a到b不经过点c的最短距离 if(ax==bx&&ay==by) return 0;//起点就是终点 memset(vis,0,sizeof(vis)); queue<node>Q; while(!Q.empty()) Q.pop(); node s;s.x=ax,s.y=ay,s.stp=0; Q.push(s); vis[ax][ay]=1; while(!Q.empty()) { node now=Q.front();Q.pop(); if(now.x==bx&&now.y==by) return now.stp; for(int i=0;i<4;i++) { node nxt; nxt.x=now.x+dx[i],nxt.y=now.y+dy[i]; if(!check(nxt.x,nxt.y)) continue; if(nxt.x==cx&&nxt.y==cy) continue; if(vis[nxt.x][nxt.y]) continue; nxt.stp=now.stp+1; Q.push(nxt); vis[nxt.x][nxt.y]=1; } } return INF;//不能到达 } void Init() { //cnt存状态标号 spfa的时候是把点看成状态 用边来表示状态的转移 //[i][j][k]是表示开始的那个点的坐标是(i,j) 空格在它的k方向 tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) if(mp[i][j]&&check(i+dx[k],j+dy[k])) cnt[i][j][k]=++tot;//给状态标号 没有标号的就是不可行的状态 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) if(cnt[i][j][k]) { int tmp; if(k==0) tmp=1; if(k==1) tmp=0; if(k==2) tmp=3; if(k==3) tmp=2; add(cnt[i][j][k],cnt[i+dx[k]][j+dy[k]][tmp],1); //连单向边就可以了 后面会遍历到旁边状态连回来的 //交换空白格子和起点格子 只需要一步 } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) for(int p=0;p<4;p++)//枚举起点格子相邻一圈的两个格子 if(k!=p&&cnt[i][j][k]&&cnt[i][j][p]) add(cnt[i][j][k],cnt[i][j][p],bfs(i+dx[k],j+dy[k],i+dx[p],j+dy[p],i,j)); //可以起点格子不动 而空白格子绕着它转(换方向) //如果用起点格子自己换方向 可能没那么优秀因为要绕一绕 //而且起点格子有可能会跑到一个离终点的地方去了 更不优 //而只动空白格子可能会优秀一些 因为空白格子最优(到处都是活动格子)只用走2~4步 //经过其他格子没有任何影响 因为都是1 只是空白格子变了而已 //而经过起点格子则会改变起点格子的坐标 } int dis[N*N]; int spfa() { queue<int>Q; while(!Q.empty()) Q.pop(); if(sx==tx&&sy==ty) return 0; memset(dis,INF,sizeof(dis)); memset(mark,0,sizeof(mark)); for(int k=0;k<4;k++) {//空格先走到起点的四周 初始状态 以空格从起点四周开始 if(cnt[sx][sy][k]) { dis[cnt[sx][sy][k]]=bfs(ex,ey,sx+dx[k],sy+dy[k],sx,sy); Q.push(cnt[sx][sy][k]); mark[cnt[sx][sy][k]]=1; } } while(!Q.empty()) { int u=Q.front();Q.pop(); mark[u]=0; for(int i=0;i<G[u].size();i++) { int v=G[u][i].first,w=G[u][i].second; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!mark[v]) { Q.push(v); mark[v]=1; } } } } //空格在哪里不用管 起点格子到了就可以 //从空格在起点格子四周随便哪个地方的状态到空格在终点格子四周随便哪个地方的状态 int res=INF; for(int k=0;k<4;k++) if(cnt[tx][ty][k]) res=min(res,dis[cnt[tx][ty][k]]); if(res==INF) return -1;//走不到 return res; } int main() { n=rd(),m=rd(),q=rd(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[i][j]=rd(); Init(); while(q--) { ex=rd(),ey=rd(),sx=rd(),sy=rd(),tx=rd(),ty=rd(); printf("%d\n",spfa()); } return 0; }