文章
16
粉丝
0
获赞
43
访问
2.7k
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int dir[4][2] = {0,1,0,-1,1,0,-1,0}; // 方向数组
char mpt[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int sx,int sy,int m,int n)
{
vis[sx][sy] = true;
for(int i = 0;i < 4;++i)
{
int nx = sx + dir[i][0];
int ny = sy + dir[i][1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny])
{
if(mpt[sx][sy] == '1')
dfs(nx,ny,m,n);
}
}
}
int main()
{
memset(mpt,0,sizeof(mpt));
memset(vis,false,sizeof(vis));
int m,n;
cin >> m >> n;
for(int i = 0;i<m;++i)
{
for(int j = 0;j < n;++j)
{
cin >> mpt[i][j];
}
}
int cnt = 0;
for(int i = 0;i<m;++i)
{
for(int j = 0;j < n;++j)
{
if(mpt[i][j] == '1' && !vis[i][j])
{
cnt++;
dfs(i,j,m,n);
}
}
}
cout << cnt << endl;
}
dfs检验连通性,套模板就行
登录后发布评论
暂无评论,来抢沙发