记录编号	313357	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2013]华容道	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.669 s
提交时间	2016-09-29 14:34:37	内存使用	0.40 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1010,maxl=99999999;
int n,m,q,f[50][50];
int dist[N][4][4];
struct point{
	int x,y;
	point(int X=0,int Y=0){x=X;y=Y;}
	inline bool operator == (const point &X){
		return x==X.x&&y==X.y;
	}
	inline point operator + (const point &X){
		return point(x+X.x,y+X.y);
	}
}v[4]={point(1,0),point(-1,0),point(0,1),point(0,-1)};
inline bool check(point x){return x.x>0&&x.x<=n&&x.y>0&&x.y<=m&&f[x.x][x.y];}
inline int P(point x){return (x.x-1)*m+x.y;}
int dis[N];
void clear(){
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		dis[P(point(i,j))]=maxl;
}
void bfs1(point x){
	dis[P(x)]=0;
	queue<point> Q;
	Q.push(x);
	while (!Q.empty()){
		point x=Q.front();int now=P(x);Q.pop();
		for (int i=0;i<4;i++){
			point t=x+v[i];int pos=P(t);
			if (check(t)&&dis[now]+1<dis[pos])
				dis[pos]=dis[now]+1,Q.push(t);
		}
	}
}
int D[N][4];bool vis[N][4];
struct sit{
	point x;int p,d;
	sit(point X=point(0,0),int pos=0){x=X;p=pos;d=D[P(x)][p];}
	bool operator > (const sit &x)const{return d>x.d;}
};
void dijsktra(point S,point T){
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	for (int k=0;k<4;k++)
		D[P(point(i,j))][k]=maxl;
	memset(vis,0,sizeof vis);
	priority_queue<sit,vector<sit>,greater<sit> > Q;
	for (int k=0;k<4;k++){
		point t=S+v[k];
		if (check(t)) D[P(S)][k]=dis[P(t)],Q.push(sit(S,k));
	}
	while (!Q.empty()){
		sit x=Q.top();int now=P(x.x),p=x.p;Q.pop();
		if (vis[now][p]) continue;
		if (x.x==T) return;
		for (int k=0;k<4;k++){//将棋子沿着向量v[k]移动 
			point t=x.x+v[k];int to=(k&1?k-1:k+1),pos=P(t);
			if (!check(t)) continue;
			if (D[pos][to]>D[now][p]+dist[now][p][k]+1){
				D[pos][to]=D[now][p]+dist[now][p][k]+1;
				Q.push(sit(t,to));
			}
		}
	}
}
int main()
{
	freopen("PuzzleNOIP2013.in","r",stdin);
	freopen("PuzzleNOIP2013.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		scanf("%d",&f[i][j]);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		point x(i,j);int now=P(x);
		if (!check(x)) continue;
		for (int k=0;k<4;k++){
			point t=x+v[k];
			if (!check(t)) continue;
			clear();dis[P(x)]=-1;bfs1(t);
			for (int l=0;l<4;l++) dist[now][k][l]=dis[P(x+v[l])];
		}
	}
	while (q--){
		int a,b,c,d,e,f;
		scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
		point E(a,b),S(c,d),T(e,f);
		if (S==T){puts("0");continue;}
		clear();dis[P(S)]=-1;bfs1(E);dijsktra(S,T);
		int ans=maxl;
		for (int k=0;k<4;k++) ans=min(ans,D[P(T)][k]);
		printf("%d\n",ans==maxl?-1:ans);
	}
	return 0;
}