题面

分析

不要被题干迷惑了，其实这就是水题一道
由题意可知，只能从0到相邻的1或从1到相邻的0
这个限制条件有可能将图划分为几个部分，每个部分之间相互连通，而部分与部分之间不能连通，就像强连通分量一样
问题其实也可以转化为输出点（i,j）所在强连通分量包含的点的个数
于是我们建好图后，对于每一次询问都bfs一次，找出这个点所在的强连通分量的范围，然后用一个数组来保存这个分量的点的个数
于是当询问到的点和以前bfs过的点在同一个强连通分量时就不用再bfs一遍了

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,st,end) for(int i=st;i<=end;i++)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define min(a,b) ((a>b)?b:a)
int n,m,cnt=1;
const int maxn=1000+5;
int g[maxn][maxn];
int tuan[maxn][maxn];
int num[maxn*maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{int x;int y;int count;};
inline int read()
{
   int ans=0;
   char r=getchar();bool neg=false;
   while(r<'0'||r>'9'){if(r=='-')neg=true;r=getchar();}
   while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
   return (neg)?-ans:ans;
}
void debug()//不要管它，它只是一个可怜的调试模块
{
	printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>debug\n");
	loop(i,1,50)printf("%d ",num[i]);
	printf("\n");
	return;
	loop(i,0,n+1)
	{
		loop(j,0,n+1)printf("%3.d",tuan[i][j]);
		printf("\n");
	}
	printf("\n");
}
void bfs(node u)
{
	queue<node>q;
	q.push(u);
	while(!q.empty())
	{
		node u=q.front();q.pop();
		int nx,ny;//debug();
		loop(i,0,3)
		{
			nx=u.x+dx[i];
			ny=u.y+dy[i];
			if(tuan[nx][ny]==-1&&g[nx][ny]!=-1&&g[u.x][u.y]^g[nx][ny])
			//若新点没有越界且和旧点不是同一个数字
			//且没有被搜索过（用按位异或~单声狗操作~来判断是否同为0或1）
			//就可以拓展新节点
			{
				tuan[nx][ny]=u.count;
				num[u.count]++;
				node v;v.x=nx;v.y=ny;v.count=u.count;
				q.push(v);
			}
		}
	}
	//debug();
}
int main()
{
   //freopen("datain.txt","r",stdin);
   //freopen("dataout.txt","w",stdout);
   n=read();m=read();
   clean(tuan,-1);//tuan=>团~~~就是保存分量范围的数组~~~~~
   clean(num,0);//保存分量包含点的个数的数组
   clean(g,-1);//01矩阵（-1是边界）
   char op;
   loop(i,1,n)
   {
   		loop(j,1,n)
   		{
   		    cin>>ch;
            if(ch=='1') g[i][j]=1;
            else g[i][j]=0;
        }
   } //建图
   /*  
   loop(i,1,n)
   {
   		loop(j,1,n)
   		{
   			scanf("%c",&op);
			g[i][j]=op-'0';	
		}
		scanf("\n");
   }*/
   //不知为什么，这样写在某谷上全部RE，但本机输出又完全正确 T T
   loop(i,1,m)
   {
		int x,y;
   		x=read();y=read();//读入询问
   		if(tuan[x][y]==-1)//如果询问所在的分量还没有被搜索过就搜索
		{
			node f;f.count=cnt++;f.x=x;f.y=y;
			tuan[x][y]=f.count;
			num[f.count]++;
			bfs(f);  	
		}	
   		printf("%d\n",num[tuan[x][y]]);
   		//tuan[x][y]指询问点（x，y）所在强连通分量的标号
   		//debug();
   }
   return 0;
}
/********************************************************************
   ID:Andrew_82
   LANG:C++
   PROG:BFS
********************************************************************/

学到的东西

• 主要是想吐槽一下某谷的测评机…