比赛 4043级NOIP2022欢乐赛1st 评测结果 AAAAAAAATA
题目名称 Multiplayer Moo 最终得分 90
用户昵称 op_组撒头屯 运行时间 2.557 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-28 19:31:05
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=250+5;
const int M=1000000+5;
int fx[]={0,1,-1,0,0},fy[]={0,0,0,1,-1};
int n,cnt=0;
int mp[N][N],sz[M]={0};
int posx[M],posy[M],col[M];
bool vis[N][N]={0};
set<int>eg[M];
bool chck(int x){
	return x>=1&&x<=n;
}
void dfs(int x,int y,int c,int id){
	vis[x][y]=1;sz[id]++;
	for (int i=1;i<=4;i++){
		int tx=x+fx[i],ty=y+fy[i];
		if (!chck(tx)||!chck(ty)||vis[tx][ty])continue;
		if (mp[tx][ty]==c)dfs(tx,ty,c,id);
		else eg[id].insert(mp[tx][ty]);
	}
	return ;
}
int tmp=0;
void dfs2(int x,int y,int c1,int c2){
	vis[x][y]=1;tmp++;
	for (int i=1;i<=4;i++){
		int tx=x+fx[i],ty=y+fy[i];
		if (!chck(tx)||!chck(ty)||vis[tx][ty])continue;
		if (mp[tx][ty]==c1||mp[tx][ty]==c2)dfs2(tx,ty,c1,c2);
	}
	return ;
}
int main(){
	freopen ("multimoo_silver_18open.in","r",stdin);
	freopen ("multimoo_silver_18open.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			scanf("%d",&mp[i][j]);
		}
	}
	int ans1=0,ans2=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (!vis[i][j]){
				dfs(i,j,mp[i][j],++cnt);
				posx[cnt]=i;posy[cnt]=j;col[cnt]=mp[i][j];
				ans1=max(ans1,sz[cnt]);
			}
		}
	}
	for (int i=1;i<=cnt;i++){
		set<int>::iterator it;
		for (it=eg[i].begin();it!=eg[i].end();it++){
			tmp=0;
			memset(vis,0,sizeof(vis));
			dfs2(posx[i],posy[i],col[i],*it);
			ans2=max(ans2,tmp);
		}
	}
	printf("%d\n%d\n",ans1,ans2);
	return 0;
}