求助
查看原帖
求助
177435
警策看取楼主2020/5/24 17:35

连样例都过不去的BFS代码。

#include<bits/stdc++.h>
using namespace std;

char p[200][200];
queue<pair<int,int> > q; 
int n,m,ans=0;

bool judge(int i,int j){
	return i>0&&i<=n&&j>0&&j<=n;
}

void bfs(int x,int y){
	q.push(make_pair(x,y));
	while(!q.empty()){
		pair<int,int> p1=q.front();
		p[p1.first][p1.second]='0';
	//	cout<<p1.first<<":"<<p1.second<<" "; 
		q.pop();
		// 找出所有相邻点
		if(p[p1.first][p1.second+1]!='0'&&judge(p1.first,p1.second+1))
			q.push(make_pair(p1.first,p1.second+1));
		if(p[p1.first][p1.second-1]!='0'&&judge(p1.first,p1.second-1))
			q.push(make_pair(p1.first,p1.second-1));
		if(p[p1.first+1][p1.second]!='0'&&judge(p1.first+1,p1.second))
			q.push(make_pair(p1.first+1,p1.second));
		if(p[p1.first-1][p1.second]!='0'&&judge(p1.first-1,p1.second))
			q.push(make_pair(p1.first-1,p1.second));
	}

}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>p[i][j];
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(p[i][j]!='0'){
				bfs(i,j);
				ans++;
//				printArray();
			}
		}
	}
	cout<<ans;
	return 0;
}

样例答案是4,程序输出14。

禁止无意义回复。

2020/5/24 17:35
加载中...