BFS求助,样例过了只有10分
查看原帖
BFS求助,样例过了只有10分
649751
Blued楼主2022/8/18 15:22
#include<bits/stdc++.h>
#define int long long
using namespace std;

struct qw{
	int x,y;
};
queue <qw> q;
int n,m;
int ans;
int a[101][101];
int nx[5]={0,-1,1,0,0};
int ny[5]={0,0,0,-1,1};
bool access[101][101];

inline int read();
inline int special_read();

void bfs(int l,int r)
{
	qw st;
	st.x=l;st.y=r;
	access[l][r]=true;
	q.push(st);
	while(!q.empty())
	{
		qw now=q.front();
		for(int i=1;i<=4;i++)
		{
			qw next=now;
			next.x+=nx[i];
			next.y+=ny[i];
			if(a[next.x][next.y]==0 or access[next.x][next.y])
			continue;
			access[next.x][next.y]=true;
			q.push(next);
		}
		q.pop();
	}
}

main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		a[i][j]=special_read();
		getchar();
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	if(a[i][j]!=0 and !access[i][j])
	{
		bfs(i,j);
		ans++;
	}
	printf("%lld",ans);
	return false;
}

inline int read()
{
	int q=1,x=0;char ch=getchar();
	while(ch<'0' or ch>'9') {if(ch=='-') q=-1;ch=getchar();}
	while(ch>='0' and ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return q*x;
}

inline int special_read()
{
	char ch=getchar();
	return ch-'0';
}
2022/8/18 15:22
加载中...