记录编号	121568	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2013]华容道	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2014-09-20 14:56:56	内存使用	1.27 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
#include<queue>
using namespace std;
const int SIZEn=35,SIZEN=10010,INF=0x7fffffff/2;
int N=0;//0~N
vector<pair<int,int> > c[SIZEN];
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
}
int n,m,query;
int board[SIZEn][SIZEn]={0};
int id[SIZEn][SIZEn][4]={0};
//0123上下左右
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
pair<int,int> Q[SIZEN*10];
int btot=0;//bfs tot
int reach[SIZEn][SIZEn]={0};
int bdis[SIZEn][SIZEn]={0};
int BFS_dis(int sx,int sy,int tx,int ty){
	if(sx==tx&&sy==ty) return 0;
	btot++;
	int head=0,tail=1;
	Q[0]=make_pair(sx,sy);
	reach[sx][sy]=btot;
	bdis[sx][sy]=0;
	while(head<tail){
		int x=Q[head].first,y=Q[head].second;head++;
		for(int d=0;d<4;d++){
			int nx=x+dx[d],ny=y+dy[d];
			if(!board[nx][ny]) continue;
			if(reach[nx][ny]==btot) continue;
			if(nx==tx&&ny==ty){
				return bdis[x][y]+1;
			}
			reach[nx][ny]=btot;
			bdis[nx][ny]=bdis[x][y]+1;
			Q[tail++]=make_pair(nx,ny);
		}
	}
	return INF;
}
int f[SIZEN]={0};
bool inq[SIZEN]={0};
queue<int> SQ;
void SPFA(int S){
	memset(inq,0,sizeof(inq));
	for(int i=0;i<=N;i++) f[i]=INF;
	f[S]=0;inq[S]=true;SQ.push(S);
	while(!SQ.empty()){
		int x=SQ.front();SQ.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(f[x]+c[x][i].second<f[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					SQ.push(u);
				}
			}
		}
	}
}
int calc(int ex,int ey,int sx,int sy,int tx,int ty){//空格,起点,终点
	if(sx==tx&&sy==ty) return 0;
	if(!board[sx][sy]||!board[tx][ty]) return -1;
	int ans=INF;
	board[sx][sy]=0;
	c[0].clear();
	for(int d1=0;d1<4;d1++){
		if(!board[sx+dx[d1]][sy+dy[d1]]) continue;
		int w=BFS_dis(ex,ey,sx+dx[d1],sy+dy[d1]);
		if(w<INF) addedge(0,id[sx][sy][d1],w);
	}
	board[sx][sy]=1;
	SPFA(0);
	for(int d2=0;d2<4;d2++) ans=min(ans,f[id[tx][ty][d2]]);
	if(ans<INF) return ans;
	else return -1;
}
void work(void){
	int ex,ey,sx,sy,tx,ty;
	for(int i=1;i<=query;i++){
		scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
		printf("%d\n",calc(ex,ey,sx,sy,tx,ty));
	}
}
void makegraph(void){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!board[i][j]) continue;
			for(int d=0;d<4;d++){
				int nx=i+dx[d],ny=j+dy[d];
				if(!board[nx][ny]) continue;
				addedge(id[i][j][d],id[nx][ny][d^1],1);
				for(int e=0;e<4;e++){
					if(e==d) continue;
					if(!board[i+dx[e]][j+dy[e]]) continue;
					board[i][j]=0;
					int w=BFS_dis(nx,ny,i+dx[e],j+dy[e]);
					if(w<INF){
						addedge(id[i][j][d],id[i][j][e],w);
					}
					board[i][j]=1;
				}
			}
		}
	}
}
void read(void){
	scanf("%d%d%d",&n,&m,&query);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&board[i][j]);
			for(int d=0;d<4;d++) id[i][j][d]=++N;
		}
	}
}
int main(){
	freopen("PuzzleNOIP2013.in","r",stdin);
	freopen("PuzzleNOIP2013.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}