P7479
业余五段来了
想不到我一个业余五段竟然被两个业余四段出的题卡了好久才过...
作为一个小学的时候（也好久不下了）下了六年围棋的选手，我上来看到这题的第一反应就是找眼。什么是眼呢？概念我也忘了就是指由黑棋与边界围成的范围（白棋不能把里面填满；黑棋与黑棋围起来的也行）
比如下面这几个图形中黑棋围起来的中间的部分就是眼
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
.****
*...*
*...*
*...*
*****
*/