555wa0分,求助,自己感觉思路没啥问题
查看原帖
555wa0分,求助,自己感觉思路没啥问题
1064432
JiaL楼主2023/11/15 18:04
#include<bits/stdc++.h>
using namespace std;
int x,y;
const int N=510;
char a[N][N];
bool gone[N][N]={false};
int X[]={0,0,1,-1};
int Y[]={1,-1,0,0};
int ans=0;
struct node{
	int xx,yy;
};
bool check(int i,int j){
	if(i<1||j<1||i>x||j>y)return false;
	if(gone[i][j])return false;
	if(a[i][j]=='*')return false;
	return true;
}
int bfs(int i,int j){
	queue<node> q;
	gone[i][j]=true;
	q.push({i,j});
	int cn=1;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.xx==1||t.yy==1||t.xx==x||t.yy==y){
			cn=0;
			return cn;
		}
		for(int i=0;i<4;i++){
			int xi=t.xx+X[i];
			int yi=t.yy+Y[i];
			if(check(xi,yi)){
				gone[xi][yi]=true;
				q.push({xi,yi});
				cn++;
			}
		}	
	}
	return cn;
}
int main(){
	scanf("%d %d",&x,&y);
	for(int i=1;i<=x;i++){
		getchar();
		for(int j=1;j<=y;j++){
			a[i][j]=getchar();
		}
	}
	for(int i=2;i<x;i++){
		for(int j=2;j<y;j++){
			if(a[i][j]=='0'&&!gone[i][j]){
				ans+=bfs(i,j);
			}
		}
	}
	printf("%d",ans);
	return 0;	
}
2023/11/15 18:04
加载中...