zqh_7plus @ 2024-05-09 22:22:02
#include<bits/stdc++.h>
using namespace std;
struct q{
int x,y;
};
queue<q> g;
int n=0,m=0,mg[1005][1005]={},fw[1005][1005]={},dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},numm=0,flag[1005][1005]={},qwe=0,bh=0,flagg[100001]={};
void BFS(){
while(!g.empty()){
++numm;
int x=g.front().x,y=g.front().y;
flag[x][y]=qwe;
flagg[qwe]++;
for(int i=0;i<=3;i++){
int nx=x+dx[i],ny=y+dy[i];
if(fw[nx][ny]==-1&&mg[x][y]!=mg[nx][ny]&&nx>=1&&ny>=1&&nx<=n&&ny<=n){
g.push(q{nx,ny});
fw[nx][ny]=1;
}
}
g.pop();
}
}
bool pd(int a,int b){
if(flag[a][b]!=-1){
bh=flag[a][b];
return true;
}
return false;
}
int main()
{
memset(flag,-1,sizeof(flag));
ios::sync_with_stdio(false);
cin>>n>>m;
char num[1005];
for(int i=1;i<=n;i++){
cin>>num;
for(int l=0;l<n;l++){
mg[i][l+1]=num[l]-'0';
}
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
if(pd(a,b)){
cout<<flagg[bh]<<endl;
}else{
numm=0;
memset(fw,-1,sizeof(fw));
g.push(q{a,b});
fw[a][b]=1;
++qwe;
BFS();
cout<<numm<<endl;
}
}
return 0;
}
求助大佬!