自动搬运

查看原文

来自洛谷，原作者为

	Jairon314 山无数，乱红如雨，不记来时路 | 这个人退役了，这也是没办法的事呀！⎝o_o⎠

搬运于2025-08-24 22:30:16，当前版本为作者最后更新于2021-04-10 07:19:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

业余五段来了

想不到我一个业余五段竟然被两个业余四段出的题卡了好久才过...

作为一个小学的时候（也好久不下了）下了六年围棋的选手，我上来看到这题的第一反应就是找眼。什么是眼呢？概念我也忘了就是指由黑棋与边界围成的范围（白棋不能把里面填满；黑棋与黑棋围起来的也行）

比如下面这几个图形中黑棋围起来的中间的部分就是眼

2 3
*.*
***

3 3
***
*.*
***

3 3
***
*.*
**.

3 4
****
*..*
****

知道了眼的概念以后，我们发现当黑棋与白棋交替下棋的时候，如果这块黑棋又两颗眼，那么白棋是不能杀掉黑棋的。可是我们发现这种方法马上被hack了——因为白棋是可以连续下的。看下面这个棋盘

7 5
*******
****.**
*.*...*
****.**
*******

这里黑棋有两颗眼，但是右边的梅花五中白棋可以把边界填上，在下一个棋子放入左边的眼中，黑棋就死了。

于是我又想到了一种方法，不考虑白棋能不能下，用白棋把黑棋的气都填上（如果白棋下的地方不是黑棋的气，那就对黑棋没有威胁了）。最后，如果白棋的方案是合法的，那黑棋一定是死的，否则是活的。

#include <iostream>
#include <cstring>
#include <cstdio>

#define int long long

#define rep(i,a,b) for(register int i(a);i^(b+1);++i)

/***************快读***************/

namespace IO {
char buf[1<<21], *p1 = buf, *p2 = buf, buf1[1<<21];
inline char gc () {return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}

#ifndef ONLINE_JUDGE
#endif

#define gc getchar

template<class I>
inline void read(I &x) {
    x = 0; I f = 1; char c = gc();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc(); }
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = gc(); }
    x *= f;
}

template<class I>
inline void write(I x) {
    if(x == 0) {putchar('0'); return;}
    I tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0) {
        buf1[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while(cnt > 0) putchar(buf1[--cnt]);
}

#define in(x) read(x)
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')

} using namespace IO;

/***************快读***************/

#define maxn 5010

int t,n,m;
char map1[maxn][maxn];
bool vis[maxn][maxn];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

//dfs求白棋的气判断死活
inline bool dfs(register int x,register int y){
	vis[x][y]=1;
	register bool flag=false;
	for(register int i=0;i^4;++i){
		register int NewX=x+dx[i];
		register int NewY=y+dy[i];
		if(map1[NewX][NewY]=='.'){
			flag=1;
		}
		if(NewX>0&&NewY>0&&NewX<=n&&NewY<=m&&!vis[NewX][NewY]&&map1[NewX][NewY]=='@'){
			flag|=dfs(NewX,NewY);
		}
	}
	return flag;
}

signed main(){
	read(t);
	while(t--){
		read(n),read(m);
		for(register int i=0;i<=n+1;++i){
			for(register int j=0;j<=m+1;++j){
				map1[i][j]=';';
				vis[i][j]=false;
			}
		}
		for(register int i=1;i<=n;++i){
			for(register int j=1;j<=m;++j){
				std::cin>>map1[i][j];
			}
		}
		for(register int i=1;i<=n;++i){
			for(register int j=1;j<=m;++j){
				if(map1[i][j]=='*'){
					if(map1[i][j+1]=='.'){
						map1[i][j+1]='@';
					}
					if(map1[i+1][j]=='.'){
						map1[i+1][j]='@';
					}
					if(map1[i][j-1]=='.'){
						map1[i][j-1]='@';
					}
					if(map1[i-1][j]=='.'){
						map1[i-1][j]='@';
					}
				}
			}
		}//这段代码把黑棋的气全变成白棋
		register int cnt=0;
		for(register int i=1;i<=n;++i){
			for(register int j=1;j<=m;++j){
				if(cnt>=2){//如果白棋有大于等于一个地方是非法的，直接退出，黑棋是活的
					j=m+1,i=n+1;
					continue;
				}
				if(map1[i][j]=='@'){
					if(!vis[i][j]&&!dfs(i,j)){
						++cnt;
						// std::cout<<i<<" "<<j<<endl;
					}
				}
			}
		}
		if(cnt>=2){
			puts("YES");
		}
		else{
			puts("NO");
		}
	}
	return 0;
}


/*
10
5 5
.****
*...*
*...*
*...*
*****
*/