记录编号	455840	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1442.[NOIP 2013]华容道	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2017-10-03 11:07:19	内存使用	21.71 MiB

#pragma GCC optimize ("O3")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define oo 0x3f3f3f3f
template<typename _t>
inline _t read() {
	_t s=0,f=1;
	char ch=getchar();
	for( ; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
	for( ; isdigit(ch); ch=getchar()) s=s*10+(ch^48);
	return s*f;
}

int n,m,q,map[35][35],r[4005],tot,num[35][35][4],sum;
int xx[4]= {1,-1,0,0},yy[4]= {0,0,1,-1};
bool vis[35][35];
struct edge {
	int fr,to,next,vv;
} c[40005];
void add(int x,int y,int z) {
	c[tot]=(edge) {
		x,y,r[x],z
	};
	r[x]=tot++;
}
int head,tail,fsx[4000005],fsy[4000005],fst[4000005],ex,ey,sx,sy,tx,ty;
int bfs(int fx,int fy,int tx,int ty,int bx,int by) {
	if(fx==tx&&fy==ty) {
		return 0;
	}
	memset(vis,0,sizeof(vis));
	head=0,tail=1;
	fsx[tail]=fx,fsy[tail]=fy,fst[tail]=0;
	vis[fx][fy]=true;
	while(head<tail) {
		register int x=fsx[++head],y=fsy[head],t=fst[head];
		for(register int k=0; k<4; ++k) {
			if(map[x+xx[k]][y+yy[k]]&&(x+xx[k]!=bx||y+yy[k]!=by)&&!vis[x+xx[k]][y+yy[k]]) {
				if(x+xx[k]==tx&&y+yy[k]==ty) {
					return t+1;
				}
				fsx[++tail]=x+xx[k];
				fsy[tail]=y+yy[k];
				fst[tail]=t+1;
				vis[x+xx[k]][y+yy[k]]=true;
			}
		}
	}
	return oo;
}
int dis[4005];
int queue[4000000];
int spfa() {
	if(sx==tx&&sy==ty) return 0;
	for(register int i=0; i<=tot; ++i) {
		dis[i]=oo;
	}
	for(register int k=0; k<4; ++k)
		if(num[sx][sy][k]) {
			dis[num[sx][sy][k]]=bfs(ex,ey,sx+xx[k],sy+yy[k],sx,sy);
			//cout<<sx<<" "<<sy<<" "<<dis[num[sx][sy][k]]<<endl;
			queue[k+1]=num[sx][sy][k];
		}
	/*for(int i=1; i<=4; ++i) {
		cout<<dis[queue[i]]<<endl;
	}*/
	head=1,tail=4;
	while(head<=tail) {
		register int p=queue[head++];
		//cout<<p<<endl;
		for(register int i=r[p]; ~i; i=c[i].next)
			if(dis[c[i].to]>dis[p]+c[i].vv) {
				dis[c[i].to]=dis[p]+c[i].vv;
				queue[++tail]=c[i].to;
			}
	}
	int ans=oo;
	for(register int k=0; k<4; k++) {
		if(num[tx][ty][k]) {
			ans=min(ans,dis[num[tx][ty][k]]);
		}
	}
	return ans==oo?-1:ans;
}
int Main(){
	freopen("PuzzleNOIP2013.in","r",stdin);
	freopen("PuzzleNOIP2013.out","w",stdout);
	n=read<int>(),m=read<int>(),q=read<int>();
	memset(r,-1,sizeof(r));
	for(register int i=1; i<=n; ++i) {
		for(register int j=1; j<=m; ++j) {
			map[i][j]=read<int>();
		}
	}
	for(register int i=1; i<=n; ++i) {
		for(register int j=1; j<=m; ++j) {
			for(register int k=0; k<4; ++k) {
				if(map[i][j]&&map[i+xx[k]][j+yy[k]]) {
					num[i][j][k]=++sum;
				}
			}
		}
	}
	for(register int i=1; i<=n; ++i) {
		for(register int j=1; j<=m; ++j) {
			for(register int k=0; k<4; ++k) {
				if(num[i][j][k]) {
					add(num[i][j][k],num[i+xx[k]][j+yy[k]][k^1],1);
				}
			}
		}
	}
	for(register int i=1; i<=n; ++i) {
		for(register int j=1; j<=m; ++j) {
			for(register int k=0; k<4; ++k) {
				for(register int h=0; h<4; ++h) {
					if(k!=h&&num[i][j][k]&&num[i][j][h]) {
						add(num[i][j][k],num[i][j][h],bfs(i+xx[k],j+yy[k],i+xx[h],j+yy[h],i,j));
					}
				}
			}
		}
	}
	for(register int i=1; i<=q; ++i) {
		ex=read<int>(),ey=read<int>(),sx=read<int>(),sy=read<int>(),tx=read<int>(),ty=read<int>();
		int ans=spfa();
		printf("%d\n",ans);
	}
	return 0;
}
int hehe=Main();
int main() {
	;
}