思路
第一问可以直接在给的地图上 Flood-Fill,可以 BFS 也可以并查集找连通块,时间复杂度差不多。
第二问比较难。首先可以想到的是暴力,对于一个连通块找与它相连的另一个连通块,然后试图把这两个连通块组合,每次去计算一下。
但时间复杂度非常高,所以考虑时间复杂度低的做法。接下来介绍这种做法。
1.1 第一步
既然要给连通块找与它相连的连通块,不妨把连通块看成一个点,然后对于它相连的连通块建无向边,这样就可以较快地知道它周围的连通块。由这些连通块得到的图上每个点存在点权,点权即为对应连通块的大小。
这一步可以放在解决第一问的时候顺便做。
注意要给每个连通块重新编号,否则对于两块属于同一人但分开的连通块,你的程序会认为是同一个连通块。
1.2 第二步
对于相邻的连通块建无向边后,你便可以在得到的图里,针对每一个连通块与它相邻的连通块做 BFS 算第二问的答案,可惜还是太慢了,所以考虑更改 BFS 的方式。
容易发现一种卡掉这种做法的输入:
250
1 2 1 2 1 2 ...
2 1 2 1 2 1 ...
1 2 1 2 1 2 ...
...
在这种输入里,每一个点 BFS 都会一直扩展到整个棋盘,因此我们的算法就被卡成了 \(O(N^4)\),所以考虑更好的方法。
容易想到在这道题里,多次走重复的边没有任何意义,因此开一个 \(\texttt{map}\) 存边是否走过。
在避免走重复边的同时也要记录是否走了重复点。注意在这里 BFS 的时候,每次 BFS 前要清掉标记点的数组,而不要清掉标记边的数组。
在 BFS 内要写检查是否走到了重复边的代码,如果检查到了那么这次 BFS 没有意义,直接退出 BFS。
在每次 BFS 中,如果不能够再扩展且不是无意义的 BFS,则把 BFS 中遇到的连通块的大小求和最后和答案取 \(\max\)。
代码
前半部分将详细解释各部分代码的打法,后面一小部分会讲如何卡常通过 #9,#10,hack。
2.1 解决第一问
使用一个 \(\texttt{queue}\) 进行 BFS 找连通块,注意这里我们算出来的东西不只是连通块(务必仔细看它们的作用,第二问将非常依赖它们):
- \(tnt\) 是编号,来一个新的连通块给一个新的编号。最终的编号是互不相同的。
- \(cnt\) 用于存储该位置所在连通块的编号。
- \(is\) 用于存储该编号下的连通块的实际值。
- \(num\) 用于存储该编号表示的连通块大小。
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!vis[i][j]){
int sum=0;
vis[i][j]=1;
q.push(mp(i,j));//初始化
while(!q.empty()){
sum++;
int x=q.front().first;
int y=q.front().second;
cnt[x][y]=tnt;//告诉这个点所在连通块的编号
q.pop();//记得 pop
for(int p=0;p<4;p++){
int yh=x+dx[p],hx=y+dy[p];
if(yh>n||hx>n||yh<1||hx<1||vis[yh][hx]||a[yh][hx]!=a[x][y]){
continue;
}
vis[yh][hx]=1;
q.push(mp(yh,hx));//记得 push
}
}
num[tnt]=sum;//处理编号为 tnt 的连通块的大小
is[tnt]=a[i][j];//处理编号为 tnt 的连通块的实际值
tnt++;
ans=max(ans,sum);
}
}
}
cout<<ans<<endl;
2.2 相邻连通块建边
从这里开始,对连通块的操作都在它们的编号上进行,而不会对棋盘进行操作。
\(n^2\) 枚举任意两点,先检查它们是否在同一连通块内且在棋盘范围内(使用刚刚算出来的 \(cnt\) 检查),再用 \(\texttt{map}\) 检查分别所在的连通块是否已经建边(防止建重边提升效率)。
如果通过了所有检查,将这两个连通块间连边并标记它们已经连边。
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int p=0;p<4;p++){
int yh=i+dx[p],hx=j+dy[p];
if(yh>n||hx>n||yh<1||hx<1||cnt[yh][hx]==cnt[i][j]){
continue;
}
if(mup.count(mp(cnt[i][j],cnt[yh][hx]))){
continue;
}
vp[cnt[i][j]].push_back(cnt[yh][hx]);
vp[cnt[yh][hx]].push_back(cnt[i][j]);
mup[mp(cnt[i][j],cnt[yh][hx])]=mup[mp(cnt[yh][hx],cnt[i][j])]=1;
}
}
}
连完边之后,连通块就变成了点,相邻的连通块建了边,原题就变成了图论。
2.3 对于每个点枚举每个与它相邻的点
这一步比较复杂,因此再做拆分讲解。
在这一段里面,点和连通块的意思是一样的。
2.3.1 BFS 之前的准备
用一个 \(\texttt{map}\)(此处的 \(muup\)) 去标记走过的边。还要使用一个数组(此处的 \(muuup\))去标记走过的点。BFS 开始之前要初始化。
使用 q1=queue<int>()
可以高效率地清空队列。
for(int i=1;i<tnt;i++){
for(int j=0;j<vp[i].size();j++){
int tql=vp[i][j];//取出相邻点
if(muup.count(mp(i,tql))){//若这两点间的边曾经走过,直接判定这次 BFS 没有意义。
continue;
}
memset(muuup,0,sizeof(muuup));//把清空放在判定之后可以减少很多无意义的清空,正是因此,我在这里卡常卡了很久
int sum=num[i]+num[tql];//sum 初始值为两个连通块的大小和,后面我们扩展的时候不会计算初始的两个连通块
muuup[tql]=muuup[i]=true;//标记初始的两个连通块已经被走过。
muup[mp(i,tql)]=muup[mp(tql,i)]=true;//标记这两个连通块之间的边走过
q1=queue<int>();
q1.push(i);
q1.push(tql);
//在这里接 2.3.2 的程序
}
}
2.3.2 BFS 的扩展
使用一个 \(\texttt{bool}\) 型变量(这里的 \(f\))标记这次 BFS 是否无意义。如果被标记了那么接下来的 BFS 内容都不能继续。最终退出取相邻点的循环后,程序会直接回到选两个相邻连通块的循环。
在 BFS 的过程中,每次扩展与我们之前选的连通块有相同颜色的点进行扩展(如之前选的颜色为 \(3,1\) 的两个连通块,那么扩展过程中我们只能走颜色为 \(3,1\) 的点)。
while(!q1.empty()){
int x=q1.front();
q1.pop();
for(int k=0;k<vp[x].size();k++){
int tqll=vp[x][k];
if(f||muuup[tqll]||(is[tqll]!=is[i]&&is[tqll]!=is[tql])){//这里筛除了被走过的点和颜色不行的点,这里说明了 is 数组的作用
continue;
}
if(muup[mp(x,tqll)]){//走到了曾经走过的边,标记这次 BFS 无意义。
f=true;
}
if(!f){
muuup[tqll]=1;//标记这个点已经走过
muup[mp(x,tqll)]=muup[mp(tqll,x)]=1;//标记这条边已经走过
q1.push(tqll);//扩展这个新点
sum+=num[tqll];//sum 要加上这个连通块的大小。
}
}
if(f){
break;//退出 BFS 的过程
}
}
if(!f){//只有在 BFS 有效时才将 sum 和目前的答案比较
ans2=max(ans2,sum);
}
最后把这份代码交上去,你会发现无论是原题记录还是测试讨论区 hack 的记录,最慢都跑了 \(900ms\) 以上。因此你可以进行一些常数优化避免因为电脑配置的不同超时。
2.4 简单的剪枝
容易发现这道题里面,若算出的答案达到了棋盘大小的一半那么这个答案将会是最终答案,不必继续 BFS。因此可以将这个代码:
if(!f){
ans2=max(ans2,sum);
}
变成
if(!f){
if(sum>=sq){
cout<<sum<<endl;
return 0;
}
ans2=max(ans2,sum);
}
注意这里要在前面加上一句sq=(n*n)>>1
。
于是原题的记录中测试点 9 跑到了 \(500ms\),测试点 10 也空出了 \(50ms\)。
hack 的记录也跑到了 \(500ms\)。
AC CODE
代码已经分段给出。