可能有点长

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;
struct st{
	int x,y;
};
int n,m,sum;
int ma[N][N],dp[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs(int x,int y){
	queue<st>q,qq;
	q.push({x,y});
	while(!q.empty()){
		st t=q.front();
		q.pop();
		if(dp[t.x][t.y]!=0)continue;
		sum++;
		qq.push({t.x,t.y});
		dp[t.x][t.y]=-1;
		for(int i=0;i<4;i++){
			int xx=t.x+dx[i];
			int yy=t.y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&dp[xx][yy]==0&&ma[t.x][t.y]!=ma[xx][yy])
				q.push({xx,yy});
		}
	}
	st t;
	while(!qq.empty()){
		t=qq.front();
		qq.pop();
		dp[t.x][t.y]=sum;
	}
}
char chs[N];
int main() {
	scanf("%d %d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++){
		scanf("%s",chs);
		for(int j=0;j<n;j++)
			ma[i][j+1]=chs[j]-'0';
		getchar();
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(dp[i][j]==0){
				sum=0;
				bfs(i,j);
			}
	int x,y;
	while(m--){
		scanf("%d %d",&x,&y);
		printf("%d\n",dp[x][y]);
	}
	return 0;
}

这个题本质上是flood fill 变形+记忆化搜索 有m个读入数据，每次bfs或者dfs必然会超时 就把之前已经搜过的点标记一下，然后这个算是01相邻的一个连通块，这个实质上就是求哪一块01连通块里面元素的个数 bfs

#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PAII;
int n,m;
const int N=1010,M=1e6+10;
char ch[N][N];
int f[N][N],cnt[M];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int bfs(int x,int y,int u)
{
queue<PAII> q;
q.push({x,y});
cnt[u]=1;
f[x][y]=u;//看看是第几层
while(q.size())
{
auto t=q.front();
q.pop();
int a=t.first,b=t.second;
for(int i=0;i<4;i++)
{
int xx=a+dx[i],yy=b+dy[i];
if(xx<0||yy<0||xx>=n||yy>=n) continue;
if(ch[a][b]-'0'==!(ch[xx][yy]-'0')&&f[xx][yy]==-1)
{
q.push({xx,yy});
cnt[u]++;
f[xx][yy]=u;
}
}
}
return cnt[u];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>ch[i][j];
memset(f,-1,sizeof(f));
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
a--;
b--;
if(f[a][b]==-1)
{
int t=bfs(a,b,i);
//cout<<t<<endl;
cnt[i]=t;
}
else cnt[i]=cnt[f[a][b]];
}
for(int i=0;i<m;i++) cout<<cnt[i]<<endl;
return 0;
}

dfs

#include<cstring>
using namespace std;
const int N=5050;
int res[100000],f[N][N];//答案和标记 
char ch[N][N];
int n,m;
void dfs(int r,int c,int z,int l)
{
	if(r<0||c<0||r>=n||c>=n||f[r][c]!=-1||ch[r][c]-'0'!=z) return ;
	f[r][c]=l;//
	res[l]++;
	dfs(r-1,c,!z,l);
	dfs(r+1,c,!z,l);
	dfs(r,c-1,!z,l);
	dfs(r,c+1,!z,l);
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>ch[i][j];
	memset(f,-1,sizeof(f));
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		if(f[a][b]==-1) dfs(a,b,ch[a][b]-'0',i);
		else res[i]=res[f[a][b]];
	}
	for(int i=0;i<m;i++) cout<<res[i]<<endl;
	return 0;
}
/*
确实可以用dfs，但如果每一次输入都来一次dfs，那必定超时
所以考虑把每一个点的答案都记录下来，如果没被记录就来一次dfs，可以就直接用 
*/