我的主要思路:
先便利一遍所有点,找到所有眼(包括边上的),然后如果在眼中有一个或以上的点的四周都没有黑棋,那么说明白旗可以用某种方式,以这个点为气将这个眼填上,所以将这个点所在的眼填上。然后统计剩余的眼的数量,如果大于等于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;
}