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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define oo 0x3f3f3f3f
char buf[40005*30], *ptr=buf-1;
inline int read(){
    register int x=0,f=1,c=*++ptr;
    while (c<48) c=='-'&&(f=-1),c=*++ptr;
    while (c>47) x=x*10+c-48,c=*++ptr;
    return x * 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) {
		int x=fsx[++head],y=fsy[head],t=fst[head];
		for(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(int i=0; i<=tot; ++i) dis[i]=oo;
	for(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);
			queue[k+1]=num[sx][sy][k];
		}
	head=1,tail=4;
	while (head<=tail) {
		int p=queue[head++];
		for(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(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);
	fread(buf,1,sizeof(buf),stdin);
	n=read(),m=read(),q=read();
	memset(r,-1,sizeof(r));
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			map[i][j]=read();
		}
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			for(int k=0; k<4; ++k) {
				if(map[i][j]&&map[i+xx[k]][j+yy[k]]) {
					num[i][j][k]=++sum;
				}
			}
		}
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			for(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(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			for(int k=0; k<4; ++k) {
				for(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(int i=1; i<=q; ++i) {
		ex=read(),ey=read(),sx=read(),sy=read(),tx=read(),ty=read();
		int ans=spfa();
		printf("%d\n",ans);
	}
	return 0;
}
int hehe=Main();
int main() {
	
}