记录编号	193481	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2013]华容道	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2015-10-14 20:19:31	内存使用	3.96 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<deque>
using namespace std;
const int SIZEN=40,INF=0x7fffffff/2,SIZED=40*40*4;
int N,M,q,tot=0;
int id[SIZEN][SIZEN][4]={0};
int sw[SIZED];
bool mp[SIZEN][SIZEN]={0};
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
deque<pair<int,int> > s[SIZED];
void read()
{
	scanf("%d%d%d",&N,&M,&q);
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)scanf("%d",&mp[i][j]);
	for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)for(int k=0;k<4;k++) id[i][j][k]=++tot;
}
int BFS(int xf,int yf,int xt,int yt)
{
	int ans=INF;
	deque<pair<int,int> > Q;
	Q.push_back(make_pair(xf,yf));
	int qs=Q.size(),step=0;
	bool inq[SIZEN][SIZEN]={0};
	while(!Q.empty())
	{
		pair<int,int> P;
		P=Q.front();Q.pop_front();
		if(P.first==xt&&P.second==yt) {ans=step;break;}
		for(int i=0;i<4;i++)
		{
			int x=P.first+dx[i],y=P.second+dy[i];
			if(!mp[x][y]) continue;
			if(!inq[x][y])
			{
			inq[x][y]=1;
			Q.push_back(make_pair(x,y));
			}
		}
		qs--;
		if(qs==0)
		{
			qs=Q.size();
			step++;
		}
		if(step>N*M) break;
	}
	return ans;
}
void spfa()
{
	deque<int> Q;
	Q.push_back(0);
	bool inq[SIZED]={0};
	Q.push_back(0);
	inq[0]=1;
	for(int i=0;i<=tot;i++) sw[i]=INF;
	sw[0]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();inq[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			int v=s[x][i].first,w=s[x][i].second;
			if(sw[x]+w<sw[v])
			{
				sw[v]=sw[x]+w;
				if(!inq[v])
				{
					inq[v]=1;
					Q.push_back(v);
				}
			}
		}
	}
}
void add(int fr,int to,int l){	s[fr].push_back(make_pair(to,l));}
void prepare()
{
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
		{
			if(!mp[i][j]) continue;
			int nx,ny;
			for(int k=0;k<4;k++) 
			{
				nx=i+dx[k],ny=j+dy[k];
				//cout<<nx<<" "<<ny<<endl;
				if(!mp[nx][ny]) continue;
				add(id[i][j][k],id[nx][ny][k^1],1);
				for(int e=0;e<4;e++)
				{
					if(e==k) continue;
					int tx=i+dx[e],ty=j+dy[e];
					//cout<<nx<<" "<<ny<<" "<<tx<<" "<<ty<<endl;
					if(!mp[tx][ty]) continue;
					mp[i][j]=0;
					int w=BFS(nx,ny,tx,ty);
					if(w!=INF) add(id[i][j][k],id[i][j][e],w);
					mp[i][j]=1;
				}
			}
		}
}
int clac(int ex,int ey,int sx,int sy,int tx,int ty)
{
	if(ex==sx&&ey==sy) return 0;
	if(!mp[ex][ey]||!mp[sx][sy]) return -1;
	int ans=INF;
	mp[sx][sy]=0;
	s[0].clear();
	for(int i=0;i<4;i++)
	{
		int x=sx+dx[i],y=sy+dy[i];
		if(!mp[x][y]) continue;
		int w=BFS(tx,ty,x,y);
		if(w<INF) add(0,id[sx][sy][i],w);
	}
	mp[sx][sy]=1;
	spfa();
	for(int i=0;i<4;i++) ans=min(ans,sw[id[ex][ey][i]]);
	if(ans<INF) return ans;
	return -1;
}
void work()
{
	int ex,ey,sx,sy,tx,ty;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d%d%d%d",&tx,&ty,&sx,&sy,&ex,&ey);
		printf("%d\n",clac(ex,ey,sx,sy,tx,ty));
	}
}
int main()
{
	freopen("PuzzleNOIP2013.in","r",stdin);
	freopen("PuzzleNOIP2013.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}