luoguerepp @ 2024-03-07 19:15:26
#include<iostream>
#include<queue>
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
int n,m;
char g[N][N];
bool st[N][N];
int group[N][N],id;
int sum[N];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
void bfs(int x0,int y0){
queue<PII> q;
q.push({x0,y0});
st[x0][y0] = true;
group[x0][y0] = id;
int cnt = 1;
while(q.size()){
auto t = q.front();
q.pop();
int x = t.first,y = t.second;
for(int i = 0; i < 4; ++i){
int a = x + dx[i],b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= n){
if(st[a][b] || g[a][b] == g[x][y]) continue;
st[a][b] = true;
group[a][b] = id;
cnt++;
q.push({a,b});
}
}
}
sum[id++] = cnt;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i) scanf("%s",g[i] + 1);
// for(int i = 1; i <= n; ++i)
// for(int j = 1; j <= n; ++j)
// if(!st[i][j]) bfs(i,j);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
if(!st[a][b]) bfs(a,b);
printf("%d\n",sum[group[a][b]]);
}
return 0;
}
by luoguerepp @ 2024-03-07 19:16:16
group是给每个连通块分组的
by luoguerepp @ 2024-03-09 21:37:12
破案了,记录每个连通块个数的数组sum[]开太小了