玄关,并查集WA90pts 求调
查看原帖
玄关,并查集WA90pts 求调
933802
ICU152_lowa_IS8楼主2024/10/2 18:53
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1005][1005];
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
int father[1000005];
int siz[1000005];
map<int,int>mp;
int f[1005][1005];
int n;
int sp(int x,int y){
	return (x-1)*n+y;
}
int find(int x){
	if(x!=father[x])father[x]=find(father[x]);
	return father[x];
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			f[i][j]=-2;
			siz[sp(i,j)]=-2;
			father[sp(i,j)]=sp(i,j); 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int tx=0,ty=0;
			for(int k=0;k<8;k++){
				int x=i+dx[k],y=j+dy[k];
				if(x<1||x>n||y<1||y>n||a[i][j]==a[x][y])continue;
				if(a[x][y]>a[i][j])tx=true;
				else ty=true;
			}
			if(tx&&ty){
				siz[sp(i,j)]=0;
			}
			if(tx&&!ty){
				siz[sp(i,j)]=-1;
			}
			else if(!tx&&ty){
				siz[sp(i,j)]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<8;k++){
				int x=i+dx[k],y=j+dy[k];
				if(x<1||x>n||y<1||y>n||a[i][j]!=a[x][y])continue;
				int fu=find(sp(i,j)),fv=find(sp(x,y));
				if(fu==fv)continue;
				father[fu]=fv;
				if(siz[fu]==-2)siz[fu]=siz[fv];
				else if(siz[fu]==1){
					if(siz[fv]==1||siz[fv]==-2)siz[fu]=1;
					else if(siz[fv]==-1||siz[fv]==0)siz[fu]=0;
				}
				else if(siz[fu]==-1){
					if(siz[fv]==-1||siz[fv]==-2)siz[fu]=-1;
					else if(siz[fv]==1||siz[fv]==0)siz[fu]=0;
				}
			}
		}
	}
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int fu=find(sp(i,j));
			if(mp[fu])continue;
			mp[fu]=true;
			if(siz[fu]==1)ans1++;
			else if(siz[fu]==-1)ans2++;
			else if(siz[fu]==-2)ans1++,ans2++;
		}
	}
	cout<<ans1<<" "<<ans2;
	return 0;
}
/*
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
2 1
*/
2024/10/2 18:53
加载中...