WA(并查集做法)求调
  • 板块P1767 家族
  • 楼主HIMkythen
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/29 21:34
  • 上次更新2024/7/29 23:11:49
查看原帖
WA(并查集做法)求调
359154
HIMkythen楼主2024/7/29 21:34
#include<bits/stdc++.h>
using namespace std;
#define MAXN 20005
int n,ans,l[201];
string st;
int a[MAXN];
char mp[201][201];
int find(int x){
	if(x==a[x]) return a[x];
	else{
		a[x]=find(a[x]);
		return a[x];
	}
	//return a[x];
}

void group(int p,int q){
    if(find(p)!=find(q)) a[find(q)]=find(p);
}
int main(){
	cin>>n;
	for(int i=1;i<=n+1;i++){
        getline(cin,st);
        l[i]=st.size();
        for(int j=1;j<=l[i];j++){
        	mp[i][j]=st[j-1];
        	a[(i-1)*l[i]+j]=(i-1)*l[i]+j;
        }
    }/*
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=l[i];j++){
        	cout<<mp[i][j];
        	
        }
        cout<<endl;
        
    }*/
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l[i];j++){
			if(mp[i][j]>=97&&mp[i][j]<=122){
                int pp = (i-1)*l[i]+j;
                if(mp[i][j+1]>=97&&mp[i][j+1]<=122)group(pp,pp+1);
                if(mp[i][j-1]>=97&&mp[i][j-1]<=122)group(pp,pp+l[i]);
                if(mp[i+1][j]>=97&&mp[i+1][j]<=122)group(pp,pp-1);
                if(mp[i-1][j]>=97&&mp[i-1][j]<=122)group(pp,pp-l[i]);
            }
		}
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<=l[i];j++){
            if(mp[i][j]>=97&&mp[i][j]<=122&&a[(i-1)*l[i]+j]==(i-1)*l[i]+j){
            	ans++;
            	cout<<i<<" "<<j<<endl;
            }
    	}
    }
    cout<<ans;
	return 0;
}
2024/7/29 21:34
加载中...