_hsk121212_ @ 2024-02-22 12:00:20
RT.
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y;
}q[1000001];
char g[1001][1001];
int n,m,sx,sy;
bool us[1001][1001];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s%*c",g[i]+1);
while(m--){
memset(us,0,sizeof(us));
memset(q,0,sizeof(q));
int k=0,e=1,f=1;
scanf("%d %d",&sx,&sy);
q[1].x=sx,q[1].y=sy;
while(f<=e){
point u=q[f++];
for(int i=0;i<4;i++){
point v;
v.x=u.x+dx[i],v.y=u.y+dy[i];
if(v.x<1||v.x>n||v.y<1||v.y>n) continue;
if(us[v.y][v.x]) continue;
if(g[v.y][v.x]==g[u.y][u.x]) continue;
q[++e]=v;
us[v.y][v.x]=1;
}
}`
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(us[j][i]) k++;
}
}
printf("%d\n",k);
}
return 0;
}
by masonxiong @ 2024-02-23 15:09:16
复杂度严重不对,光 bfs 初始化的复杂度就达到了
这题得动动脑子,直接暴力肯定挂
by zzx1228 @ 2024-03-07 16:31:28
给个思路吧:
应该是先找连通块,整体赋值,最后的询问提前记录可以直接给答案