先广搜,标记每一次搜索到连通块搜索过、同一搜索序列号,搜索过程记录搜索区域面积,搜索一遍完成将面积计入到ans数组里,最后通过某一区域标记的搜索序列号访问ans找到搜索区域面即QAQ感觉思路没错呀,球球救救我
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<cmath>
using namespace std;
int n,m;
int mp[1005][1005];
int ans[1001];
int num=2;
struct def_point{
int x,y;
};
def_point que[100005];
int x_dir[4]={0,0,-1,1};
int y_dir[4]={-1,1,0,0};//方向数组
int cnt=0;
bool ck[1005][1005];
void bfs(int x,int y){
int ct=0;
int st=0,ed=1;
def_point row[1005];
memset(row,0,sizeof(row));
row[ed].x=x;row[ed].y=y;
++ed;
ck[x][y]=false;
while(st!=ed){
++st;
for(int j=0;j<=3;++j){
int xx=row[st].x+x_dir[j];
int yy=row[st].y+y_dir[j];
if( xx<=n && xx>0 && yy<=n && yy>0 &&
ck[xx][yy] &&
mp[xx][yy]!=mp[row[st].x][row[st].y]){
row[ed].x=xx;row[ed].y=yy;
++ed;
ck[xx][yy]=false;
}
}
mp[row[st].x][row[st].y]=num;
//将每一区域写为第num号索引,之后以便在ans里查找
}
cnt=st-1;//cnt记录本次搜索联通区域的大小
}
void check_mp(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cout<<mp[i][j];
}
cout<<endl;
}
}
int main(){
char qaq;
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin>>qaq;
mp[i][j]=int(qaq);
}
}
for(int i=1;i<=m;++i){
cin>>que[i].x>>que[i].y;
}
memset(ck,true,sizeof(ck));
//数据输入完毕
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(ck[i][j]){
bfs(i,j);
ans[num]=cnt;
++num;
}
}
}
for(int i=1;i<=m;++i){
cout<<ans[mp[que[i].x][que[i].y]]<<endl;
}
return 0;
}