记录编号	544929	评测结果	AAAAAAAAAAAAAATTAATT
题目名称	[NOIP 2013]华容道	最终得分	80
用户昵称	Hale	是否通过	未通过
代码语言	C++	运行时间	5.511 s
提交时间	2019-10-23 21:49:51	内存使用	112.56 MiB

#include <bits/stdc++.h>
using namespace std;
 
const int Max=31;
const int fx[5]={0,1,0,-1,0};
const int fy[5]={0,0,1,0,-1};
int n,m,ans,q;
int sx,sy,tx,ty,x,y;
int num[Max][Max],vis[Max][Max][Max][Max];
struct shu{int x,y,sx,sy,step;};
shu p[5000001];
 
inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') f=-1,c=getchar();
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}
 
inline int bfs()
{
	int head=0,tail=1;
	p[1].x=x,p[1].y=y,p[1].sx=sx,p[1].sy=sy;
	while(head<tail)
	{
	  int x=p[++head].x,y=p[head].y;
	  for(int i=1;i<=4;i++)
	  {
	  	int x1=x+fx[i],y1=y+fy[i],xx=p[head].sx,yy=p[head].sy;
	  	if(x1==xx&&y1==yy) xx=x,yy=y;
	  	if(x1<1||x1>n||y1<1||y1>m||!num[x1][y1]||vis[x1][y1][xx][yy]) continue;
	  	tail++;
	  	p[tail].sx=xx,p[tail].sy=yy,p[tail].x=x1,p[tail].y=y1,p[tail].step=p[head].step+1;
		vis[x1][y1][xx][yy]=1;
	  	if(p[tail].sx==tx&&p[tail].sy==ty) return p[tail].step;
	  }
	}
	return -1;
}
 
int main()
{
	freopen("PuzzleNOIP2013.in","r",stdin);
	freopen("PuzzleNOIP2013.out","w",stdout);
	n=get_int(),m=get_int(),q=get_int();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    num[i][j]=get_int();
	while(q--)
	{
	  memset(vis,0,sizeof(vis));
	  x=get_int(),y=get_int(),sx=get_int(),sy=get_int(),tx=get_int(),ty=get_int();
	  if(sx==tx&&sy==ty) cout<<"0\n";
	  else
	  {
	    ans=bfs();
	    cout<<ans<<"\n";
	  }
	}
	return 0;
}