记录编号	581805	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 01迷宫	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.421 s
提交时间	2023-08-13 22:35:15	内存使用	7.35 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1010;
int n,m;
int fa[N*N],s[N*N],c[N][N];
int xx[10] = {0,0,1,0,-1},yy[10] = {0,1,0,-1,0};
char ch;
bool v[N][N];
int di(int x,int y){
	return (x-1)*n+y;
}
int find(int x){
	if(fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}
void sou(int x,int y){
	v[x][y] = 1;
 	for(int i = 1;i <= 4;i++){
		int nx = x+xx[i],ny = y+yy[i];
	    if(v[nx][ny] || nx < 1 || ny < 1 || nx > n || ny > n)continue;
		if(c[x][y] == !c[nx][ny]){
			int fx = find(di(x,y)),fy = find(di(nx,ny));
			if(fx != fy){
				fa[fx] = fy;
				s[fy] += s[fx];
			}
		    sou(nx,ny);
		}
	}
}
int main(){
	freopen("maze01.in","r",stdin);
	freopen("maze01.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			fa[di(i,j)] = di(i,j);
			s[di(i,j)] = 1;
			cin>>ch;
			c[i][j] = (ch == '1');
		}
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			if(!v[i][j]){
				sou(i,j);
			}
		}
	}
	for(int i = 1;i <= m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",s[find(di(x,y))]);
	}
	
	return 0;
	
}