牛客训练营（二）

可以分开吗？

K-可以分开吗？_2025牛客寒假算法基础集训营2

这道题有一个小小的“坑”，就是题目中所说的最大连通块并不是真正的最大连通块（开始的时候没有想到这个点，所以一直不明白倒数第二个样例为什么是2），而是只要能分离的连通块都是最大连通块，所以只需要找到分离所需要敲的砖最少的连通块即可。

通过dfs来找出每一个连通块，然后统计该连通块周围的‘0’的个数，并和之前存下来的相比较，最终找到周围‘0’最少的连通块。

#include<bits/stdc++.h>
using namespace std;
// #define int long longint n,m;
char a[511][511];
int vis[511][511];
int temp;
int cnt;
int sum=0xffff;
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};void dfs(int x,int y)//dfs寻找每一个连通块周围‘0’的个数
{if(a[x][y]=='0'&&vis[x][y]!=cnt){temp++;vis[x][y]=cnt;return;}vis[x][y]=cnt;for(int i=0;i<4;i++){int xx=x+dx[i];int yy=y+dy[i];if(vis[xx][yy]==cnt||xx<1||xx>n||yy<1||yy>m)continue;//越界或者当前已经比统计到的最小的连通块还要大的时候，就放弃当前连通块dfs(xx,yy);}
}signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='1'){if(vis[i][j]==0){cnt++;vis[i][j]=cnt;temp=0;dfs(i,j);//遇到一周围是0，就统计一下sum=min(sum,temp);//找出0最少的连通块}}}}cout<<sum;
}