文章

16

粉丝

0

获赞

43

访问

2.7k

头像
岛屿数量2 题解:
P6666 北京师范大学机试题
发布于2026年3月24日 03:23
阅读数 181

#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检验连通性,套模板就行

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发