文章

59

粉丝

0

获赞

185

访问

4.1k

头像
石油储藏 题解:dfs
P1564 中国科学院大学2021年机试题
发布于2026年3月12日 22:18
阅读数 72

#include <iostream>
#include <cstring>
using namespace std;

const int maxn=105;
char mpt[maxn][maxn];
int vis[maxn][maxn];
const int dir[8][2]={0,1,1,0,0,-1,-1,0,1,1,1,-1,-1,1,-1,-1};
void dfs(int x,int y)
{
	vis[x][y]=1;
	for(int i=0;i<8;i++)
	{
		int dx=x+dir[i][0];
		int dy=y+dir[i][1];
		if(mpt[dx][dy]=='@'&&vis[dx][dy]==0)
		{
			dfs(dx,dy);
		}
	}
}
int main()
{
	int m,n;
	while(cin>>m>>n)
	{
		if(!m)
			break;
		memset(mpt,0,sizeof(mpt));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				cin>>mpt[i][j];
		int ans=0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				if(mpt[i][j]=='@'&&vis[i][j]==0)
				{
					ans++;
					dfs(i,j);
				}
		cout<<ans<<endl;
	}
	return 0;
}
	

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发