P1451 求助大佬!!!!40分代码
查看原帖
P1451 求助大佬!!!!40分代码
139509
liufukang楼主2020/12/27 15:56
#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
struct Node{
	int a,b;
};
queue<Node>q;
int g[110][110];
int n,m,ans=1,x,y;
int bfs();
int main(){
	cin>>n>>m;
	memset(g,0,sizeof(g));//保险起见,图初始化
	for (int i=1;i<=n;i++){
		string s;
		cin>>s;
		for (int j=0;j<m;j++) g[i][j]=s[j]-'0';
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (g[i][j]){
				while (!q.empty()) q.pop();//多次BFS初始化队列
				ans++;//有一个不为0的就是细菌
				x=i,y=j;
				bfs();
			}
		}
	}
	cout<<ans<<endl;//输出答案
	return 0;
}
int bfs(){
	q.push({x,y});
	g[x][y]=0;//到过的地方变成0
	while (!q.empty()){
		Node tmp=q.front(); q.pop();
		for (int i=0;i<4;i++){
			int x1=tmp.a+dx[i];
			int y1=tmp.b+dy[i];//目标点更改
			if (!g[x1][y1]) continue;//如果目标点为0就不走
			g[x1][y1]=0;//到过变0
			q.push({x1,y1});//压入队列
		}
	}
}
2020/12/27 15:56
加载中...