AcWing 691. 立方体IV
原题链接
简单
作者:
曦薇
,
2022-06-24 11:22:42
,
所有人可见
,
阅读 174
思路
- 用并查集记录次序临近且位置临近的元素,并查集的根节点是最小的元素,同时记录对应并查集的大小,遍历一遍数组元素即可找到本问题得到答案。
- 时间复杂度为 $O(K \times S^2)$ ,空间复杂度为 $O(S^2)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
int fa[N*N];
int num[N*N];
int s;
bool check(int x,int y){
if(x>=1&&x<=s&&y>=1&&y<=s) return true;
return false;
}
int find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
}
return fa[x];
}
int main(void){
int t,i,j,k;
scanf("%d",&t);
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
for(k=1;k<=t;k++){
scanf("%d",&s);
int ans1=1,ans2=1;
for(i=1;i<=s;i++){
for(j=1;j<=s;j++){
scanf("%d",&g[i][j]);
}
}
for(i=1;i<=s*s;i++){
fa[i]=i;
num[i]=1;
}
for(i=1;i<=s;i++){
for(j=1;j<=s;j++){
int tmp;
for(tmp=0;tmp<4;tmp++){
int x1=i+dx[tmp],y1=j+dy[tmp];
if(!check(x1,y1)) continue;
else if(!(g[x1][y1]-g[i][j]==1)) continue;
else{
int t1=find(g[i][j]),t2=find(g[x1][y1]);
if(t1==t2) continue;
else if(t1<t2){
fa[t2]=t1;
num[t1]+=num[t2];
if(num[t1]>ans2){
ans2=num[t1];
ans1=t1;
}
if(ans2==num[t1]&&t1<ans1) ans1=t1;
}else{
fa[t1]=t2;
num[t2]+=num[t1];
if(num[t2]>ans2){
ans2=num[t2];
ans1=t1;
}
if(ans2==num[t2]&&t2<ans1) ans1=t2;
}
}
}
}
}
printf("Case #%d: %d %d\n",k,ans1,ans2);
}
return 0;
}