CodeForces 616C The Labyrith

题目

◇题目传送门◆

题目大意

给定一个$N\times M$的矩阵，其中，字符“.”表示该节点是通路，字符“＊”表示该节点是不能通过的。现可以将一个”＊”变成一个“.”，求在对所有“＊”进行操作后，所得的最大连通块内的节点数量。

思路

非常标准的一道DFS求连通块的题目。

但是，如果我们对每个“＊”点进行DFS的话，是肯定会TLE的。。。

我们可以换一种思路，即先求出“.”连通块的大小，再对每个“＊”进行处理，即将相邻的“.”连通块的大小求和并加上1，就可得到结果了

实现细节

注意：对计算过的连通块进行判重（我就这样被坑了几次）！

正解代码

#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=1000;
const int dir[][2]={
   {
   0,1},{
   0,-1},{
   1,0},{-1,0}};int N,M;
char Map[Maxn+5][Maxn+5];int vis[Maxn+5][Maxn+5];
int cnt,pcnt;
int C[Maxn*Maxn+5];
set<int> sx;
void DFS(int x,int y) {if(vis[x][y])return;vis[x][y]=cnt;pcnt++;for(int i=0;i<4;i++) {int tx=x+dir[i][0],ty=y+dir[i][1];if(tx<1||tx>N||ty<1||ty>M)continue;if(Map[tx][ty]=='*'||vis[tx][ty])continue;DFS(tx,ty);}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d",&N,&M);for(int i=1;i<=N;i++)scanf("%s",Map[i]+1);for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)if(Map[i][j]=='.') {cnt++;pcnt=0;DFS(i,j);C[cnt]=pcnt;}for(int i=1;i<=N;i++) {for(int j=1;j<=M;j++) {if(Map[i][j]=='.') {putchar(Map[i][j]);continue;}int tmp=1;sx.clear();for(int k=0;k<4;k++) {int tx=i+dir[k][0],ty=j+dir[k][1];if(tx<1||tx>N||ty<1||ty>M)continue;if(Map[tx][ty]=='*'||sx.count(vis[tx][ty]))continue;tmp=(tmp+C[vis[tx][ty]])%10;sx.insert(vis[tx][ty]);}printf("%d",tmp%10);}puts("");}return 0;
}