样例二过了,样例一没过,全WA求助(c++bfs)
查看原帖
样例二过了,样例一没过,全WA求助(c++bfs)
741987
110802Ly楼主2023/4/1 22:32

样例一输出2,下载了测试点一,答案为标答的二分之一少一点,求助大佬

#include<bits/stdc++.h>
using namespace std;
int r,c;
char a[555][555];
int vis[555][555];
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
struct node {
	int x,y;
};
int bfs(int x,int y) {
    int cnt=1;//统计0的数量,因为起点算一个,所以cnt初始为1 
	queue<node> q;
	node start;
	start.x=x;
	start.y=y;
	q.push(start);//入队 
	vis[x][y]=1;//提前标记 
	while(!q.empty()) {
		node now=q.front();
		q.pop();
		if(now.x==0||now.x==r-1||now.y==0||now.y==c-1)	return 0;//搜到边缘,
		//                                         说明这个重要地点已被淹没。
		//                                         存活基地数为0 
		for(int i=0; i<4; i++) {
			int nx,ny;
			nx=now.x+dir[i][0];
			ny=now.y+dir[i][1];
			if(a[nx][ny]!='*'&&nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0) {
				cnt++;//走到下一步,假设基地没被淹没,数量++ 
				vis[nx][ny]=1;//标记 
				node newp= {nx,ny};
				q.push(newp);//入队 
			}
		}
	}
    return cnt;//搜到队列为空,说明真的没被淹没 
}
int main() {
	cin>>r>>c;
    int ans=0;
	for(int i=0; i<=r-1; i++) {
		for(int j=0; j<=c-1; j++) {
			cin>>a[i][j];
		}
	}
	for(int k=0; k<=r-1; k++) {
		for(int l=0; l<=c-1; l++) {
			if(vis[k][l]==0&&a[k][l]!='*') {//如果没被访问且不为墙 
				ans+=bfs(k,l);//直接加(如果被淹没bfs为0,没影响) 
			}
		}
	}
    cout<<ans;//最后输出 

	return 0;
}
2023/4/1 22:32
加载中...