点击查看代码
#include<bits/stdc++.h>
using namespace std;const int N=1005;
int n,m;
char g[N][N];
//联通块对应的id
int cid[N][N];
//连通块对应的大小
int csize[N*N];
//连通块计数器，记录有多少个连通块了，顺便对应id
int cnt;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};void bfs(int sx,int sy)
{//如果已经访问过就直接结束if(cid[sx][sy]!=0) return;cnt++;//放入首个元素queue<pair<int,int>> q;q.push({sx,sy});cid[sx][sy]=cnt;//记录大小int size=0;//搜索主程序while(!q.empty()){//取出队首auto [x,y]=q.front();q.pop();size++;char cur=g[x][y];//扩散搜索for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//检查边界，是否访问，是否符合移动规则if(nx<1||nx>n||ny<1||ny>n) continue;if(cid[nx][ny]!=0) continue;if(g[nx][ny]==cur) continue;//记录对应的idcid[nx][ny]=cnt;q.push({nx,ny});}}csize[cnt]=size;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);//读入迷宫cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cin>>g[i][j];}//预处理，找出所有连通块for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(cid[i][j]==0) bfs(i,j);}}//处理查询while(m--){int x,y;cin>>x>>y;//取出对应的连通块idint id=cid[x][y];//输出对应连通块的大小cout<<csize[id]<<endl;}return 0;
}
