记录编号	300357	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 01迷宫	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.219 s
提交时间	2016-08-28 14:12:28	内存使用	4.79 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010*1010,dx[]={0,-1},dy[]={-1,0};
int hash(int,int);
int findroot(int);
void mergeset(int,int);
int n,m,a[maxn],prt[maxn],size[maxn],x,y;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("maze01.in","r",stdin);
	freopen("maze01.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%1d",&a[hash(i,j)]);
		prt[hash(i,j)]=hash(i,j);
		size[hash(i,j)]=1;
		for(int k=0;k<2;k++){
			x=i+dx[k];
			y=j+dy[k];
			if(!x||!y||a[hash(i,j)]==a[hash(x,y)])continue;
			mergeset(hash(i,j),hash(x,y));
		}
	}
	while(m--){
		scanf("%d%d",&x,&y);
		printf("%d\n",size[findroot(hash(x,y))]);
	}
	return 0;
}
inline int hash(int x,int y){
	return x*(n+1)+y;
}
inline int findroot(int x){
	static int rt,y;
	for(rt=prt[x];prt[rt]!=rt;rt=prt[rt]);
	for(;prt[x]!=x;x=y){
		y=prt[x];
		prt[x]=rt;
	}
	return rt;
}
inline void mergeset(int x,int y){
	static int rx,ry;
	rx=findroot(x);
	ry=findroot(y);
	if(rx==ry)return;
	prt[ry]=rx;
	size[rx]+=size[ry];
}
int hzoier=MAIN();
int main(){;}