大致思路：考虑把黑棋所有的气都放上棋子，如果这些气形成的连通块中有大于等于两个连通块的附近没有空地，则答案为 YES，否则为 NO。

数据检验是一堆 WA+TLE，请问可以怎么改、优化？谢谢！

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,cnt=0;
int mp[2009][2009];
bool vis[2009][2009];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
bool dfs(int x,int y){
	vis[x][y]=true;
	for(int k=1;k<=4;k++){
		int xx=x+dx[k],yy=y+dy[k];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==false){
			if(mp[xx][yy]==0){//如果搜到了空地说明还有气
				return true;
			}
			if(mp[xx][yy]==2){
				if(dfs(xx,yy)) return true;
				else return false;
			}
		}
	}
	return false;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		cnt=0;//记录有多少个气的连通块旁边没有空地
		memset(vis,false,sizeof(vis));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char ch;
				cin>>ch;
				if(ch=='.') mp[i][j]=0;
				if(ch=='*') mp[i][j]=1;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(mp[i][j]==1){
					for(int k=1;k<=4;k++){
						int x=i+dx[k],y=j+dy[k];
						if(x<1||x>n||y<1||y>m||mp[x][y]!=0) continue;
						mp[x][y]=2;
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(mp[i][j]==2&&vis[i][j]==false){
					if(!dfs(i,j)) cnt++;
				}
			}
		}
		if(cnt<=1) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}