求助
查看原帖
求助
67493
lxzy_楼主2021/4/6 13:53

我的主要思路:

先便利一遍所有点,找到所有眼(包括边上的),然后如果在眼中有一个或以上的点的四周都没有黑棋,那么说明白旗可以用某种方式,以这个点为气将这个眼填上,所以将这个点所在的眼填上。然后统计剩余的眼的数量,如果大于等于2则为YES,否则为NO

求助问题所在

#include<cstdio>
#include<iomanip>
#include<queue>
using namespace std;
const int N=2e3+50;
struct point{int x,y;};
char a[N][N];
bool vis[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n,m,t;
inline bool Check(int x,int y)
{
	int nx,ny;
	for(int i=0;i<=3;i++){
		nx=x+dx[i],ny=y+dy[i];
		if(a[nx][ny]=='*') return false;
	}
	return true;
}
inline void Init(int x,int y)
{
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++) vis[i][j]=false;
	}
}
void BFS(int x,int y)
{
	queue<point> que;
	while(!que.empty()) que.pop();
	que.push((point){x,y});
	vis[x][y]=true;
	while(!que.empty()){
		point f=que.front();
		que.pop();
		a[f.x][f.y]='*';
		for(int i=0;i<=3;i++){
			int nx=f.x+dx[i],ny=f.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&(!vis[nx][ny])&&a[nx][ny]=='.'){
				que.push((point){nx,ny});
				vis[nx][ny]=true;
			}
		}
	}
}
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		Init(n,m);
		for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]=='.'&&Check(i,j)) BFS(i,j);
			}
		}

		int cnt=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]=='.') cnt++,BFS(i,j);
			}
		}
		if(cnt>=2) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
2021/4/6 13:53
加载中...