题目背景

YSGHYYDS

题目描述

YSGH 有一个 $n\times m$ 的围棋棋盘，初始时，每个位置要么是空的，要么有一个黑棋棋子。保证黑棋是连通的。

在围棋中，一个棋子的「气」是与它相邻的所有空位置构成的集合。

设棋盘上第 $i$ 行第 $j$ 个位置为 $(i,j)$。

两个分别在 $(i_1,j_1)$ 和 $(i_2,j_2)$ 的同色棋子如果满足 $|i_1-i_2|+|j_1-j_2|=1$，就认为是相邻的，也就是在同一个连通块里。

一个连通块的「气」是这个连通块中所有棋子的「气」的并集。

白方走一步棋是合法的，当且仅当走完这手棋之后这个棋子所在连通块的「气」大于等于 $1$ 或者黑棋连通块的「气」等于 $0$。

比如下图，绿色的位置都是黑棋连通块的「气」。

「活棋」的定义：无论对方连续走多少手棋，在每步棋都是合法的情况下，该连通块的「气」都大于等于 $1$。

请你判断这个黑棋连通块是否是「活棋」。

如果是，输出 YES，否则输出 NO。

本题有多测。

输入格式

第一行，一个正整数 $T$，表示数据组数。

对于每组数据：

第一行，两个正整数 $n, m$，表示棋盘的大小为 $n \times m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。第 $i$ 行第 $j$ 个字符表示棋盘上位置为 $(i, j)$ 的地方是否有棋子。. 表示空格，* 表示黑棋子。

输出格式

如果黑棋是「活棋」，输出 YES，否则输出 NO。

3
3 5
.*.*.
.***.
.....
2 5
.*.*.
.***.
6 5
.*...
.***.
**.**
*...*
**.**
*****

NO
YES
NO

1
1 3
.*.

YES

提示

【样例解释 #1】

第 1 组数据：

白棋依次走 $(1,1),(2,1),(3,2),(3,3),(3,4),(1,5),(2,5),(1,3)$ 即可使得黑棋连通块的「气」变成 $0$ 了。

不妨用 @ 表示白棋，那么最终局面就是：

@*@*@
@***@
.@@@.

第 2 组数据：

比方说白棋先走 $(1,1)$ 那么白棋之后就再也走不到 $(1,3)$ 和 $(2,1)$ 了，导致黑棋的「气」永远大于等于 $1$，所以黑棋是「活棋」。

第 3 组数据：

最终使得黑棋连通块的「气」等于 $0$ 的局面：

@*@@.
@***@
**@**
*@.@*
**@**
*****

---

【数据范围】

本题采用捆绑测试。

对于 $100 \%$ 的数据，$1 \le n, m \le 2 \times {10}^3$，$1 \le T \le {10}^5$。输入的初始棋盘的每个位置要么是 .，要么是 *，并且至少有一个 .，至少有一个 *。保证黑棋是连通的。 保证每个测试点的 $n \times m$ 之和都小于等于 $4 \times {10}^6$。

• Subtask 1（9 points）：$n = 1$。
• Subtask 2（10 points）：$n = 2$，$m = 3$。
• Subtask 3（16 points）：保证 . 的个数不超过 $7$，$n, m \le 10$，$T \le 50$。
• Subtask 4（24 points）：保证 . 的个数不超过 $14$，$n, m \le 10$，$T \le 50$。
• Subtask 5（15 points）：$n, m \ge 3$，输入局面的边界上都是 .。即 $\forall (i, j)$，如果 $i = 1 \lor i = n \lor j = 1 \lor j = m$，则 $(i, j)$ 一定是空地。
• Subtask 6（26 points）：无特殊限制。

---

---

---

P.S. Froggy 和 uyom 都是（很久没下棋的）业余四段哥，欢迎找我们然后把我们虐一顿。