dongzhen @ 2024-08-25 19:42:15
是否应当开放一点空间(思考) 代码如下,调不出来
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <string.h>
#define lnt long long
#define inf 0x7fffffff
using namespace std;
int xx;char ff,chh;inline int read(){
xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=1e3+2;
struct point{
int x,y;
bool operator ==(point a){return a.x==x && a.y==y;}
bool operator !=(point a){return !(*this==a);}
};
template<typename T>
#define tnt T
struct zy{
tnt g[N][N];
tnt &operator [](point a){return g[a.x][a.y];}
};
struct bcj{
zy<point> g;zy<int> siz;
bcj(){for(int i=0;i<N;++i){for(int e=0;e<N;++e){g[(point){i,e}]={i,e};}}}
point find(point a){return g[a]==a? a: g[a]=find(g[a]);}
void join(point a,point b){g[find(b)]=g[find(a)];}
}s;
zy<int> date;
int n,G;
void dfs(point);
int main(){
n=read();G=read();
for(int i=0;i<n;++i){
for(int e=0;e<n;++e){
char c=getchar();
while(c!='0' && c!='1'){c=getchar();}
date[{i,e}]=c-'0';
}
}
for(int i=0;i<n;++i){
for(int e=0;e<n;++e){
if(!s.siz[{i,e}]){
dfs({i,e});
}
}
}
while(G--){
int x=read()-1,y=read()-1;
point to=s.find({x,y});
printf("%d\n",s.siz[s.find({x,y})]);
}
return 0;
}
bool is(point a){return (a.x!=n && a.y!=n && a.x!=-1 && a.y!=-1);}
void dfs(point x){
s.siz[s.find(x)]++;
if(s.find(x)!=x){s.siz[x]++;}
point to={x.x+1,x.y};
if(is(to) && !s.siz[to] && date[to]+date[x]==1){
s.join(x,to);
dfs(to);
}
to={x.x-1,x.y};
if(is(to) && !s.siz[to] && date[to]+date[x]==1){
s.join(x,to);
dfs(to);
}
to={x.x,x.y-1};
if(is(to) && !s.siz[to] && date[to]+date[x]==1){
s.join(x,to);
dfs(to);
}
to={x.x,x.y+1};
if(is(to) && !s.siz[to] && date[to]+date[x]==1){
s.join(x,to);
dfs(to);
}
}