zzz987 @ 2024-01-20 10:17:34
#include<iostream>
#include<queue>
using namespace std;
const int N=1e3+9;
int n,m;
int a[N][N];
int p[N][N],d=0;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(a[tx][ty]==a[x][y]) continue;
if(p[tx][ty]) continue;
if(1<=tx&&tx<=n&&1<=ty&&ty<=m){
p[tx][ty]=d;
dfs(tx,ty);
}
}
}
int ans[N*N];
int main(){
cin >>m>>n;
string s;
for(int i=1;i<=n;i++){
cin >>s;
for(int j=0;j<s.size();j++){
a[i][j+1]=s[j]-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!p[i][j]){
p[i][j]=++d;
dfs(i,j);
cout <<endl;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int t=p[i][j];
ans[t]++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
p[i][j]=ans[p[i][j]];
}
}
while(m--){
int x,y; cin >>x>>y;
cout <<p[x][y]<<"\n";
}
return 0;
}
by Y_QWQ_Y @ 2024-01-20 10:23:25
@zzz987 先不说 wa 和 re,你 dfs 时间肯定会超,还有,是先
by zzz987 @ 2024-01-20 10:29:44
n和m确实错了 hh 但是我这个用p数组存搜过的地方不算记忆化吗?