BFSqueue求调,第二个测试点本地对了
  • 板块P1451 求细胞数量
  • 楼主ZXXS
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/10 19:58
  • 上次更新2023/10/27 07:58:05
查看原帖
BFSqueue求调,第二个测试点本地对了
595999
ZXXS楼主2022/10/10 19:58
#include<bits/stdc++.h>//BFS
#define debug(x) cerr<<#x<<"="<<(x)<<endl;
using namespace std;
inline void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
    return x*f;
}
int n,m;
char a[105][105];
bool dp[105][105]; 
struct node
{
	int x;
	int y;
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int ans;
queue<node> q;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
    	for(int j=1;j<=m;++j)
    		a[i][j]=getchar();
    	getchar();
	}
	for(int i=1;i<=n;++i)
    {
    	for(int j=1;j<=m;++j)
    	{
    		if(a[i][j]>'0'&&!dp[i][j])
    		{
    			q.push((node){i,j});
    			while(!q.empty())
    			{
    				a[q.front().x][q.front().y]=0;
					for(int i=0;i<4;++i)
    				{
    					if(q.front().x+dx[i]<=n&&q.front().x+dx[i]>=1&&q.front().y+dy[i]<=m&&q.front().y+dy[i]>=1&&a[q.front().x+dx[i]][q.front().y+dy[i]]>'0'&&!dp[q.front().x+dx[i]][q.front().y+dy[i]])
    						q.push((node){q.front().x+dx[i],q.front().y+dy[i]});
					}
					q.pop();
				}
				++ans;
			}			
		}
	}
	write(ans);
	putchar('\n');
    return 0;
}
2022/10/10 19:58
加载中...