P7479 To You, Who Once Were a Hero

YSGHYYDS

YSGH has an $n \times m$ Go board. Initially, each cell is either empty or contains a black stone. **It is guaranteed that all black stones are connected.** In Go, the “liberties” of a stone are defined as the set of all **empty** cells adjacent to it. Let the cell in row $i$ and column $j$ be $(i, j)$. Two **same-colored** stones at $(i_1, j_1)$ and $(i_2, j_2)$ are considered adjacent if $|i_1 - i_2| + |j_1 - j_2| = 1$, meaning they are in the same connected component. The “liberties” of a connected component are the union of the liberties of all stones in that component. A white move is legal if and only if, after placing the stone, either the liberties of the connected component containing that white stone are at least $1$, or the liberties of the black connected component become $0$. For example, in the figure below, the green cells are all liberties of the black connected component.  Definition of a “living group”: no matter how many consecutive moves the opponent makes, as long as every move is legal, the liberties of that connected component are always at least $1$. Please determine whether this black connected component is a “living group”. If it is, output `YES`; otherwise, output `NO`. **This problem has multiple test cases.**

The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains two positive integers $n, m$, meaning the board size is $n \times m$. Then follow $n$ lines, each a string of length $m$. The $j$-th character of the $i$-th line indicates whether there is a stone at position $(i, j)$. `.` means empty, and `*` means a black stone.

If the black group is “living”, output `YES`; otherwise, output `NO`.

**[Sample Explanation #1]** Test case 1: White plays $(1,1),(2,1),(3,2),(3,3),(3,4),(1,5),(2,5),(1,3)$ in order, which makes the liberties of the black connected component become $0$. Let `@` denote white stones. Then the final position is: ```plain @*@*@ @***@ .@@@. ``` Test case 2: For example, if White first plays $(1,1)$, then White will never be able to play at $(1,3)$ and $(2,1)$ afterward, causing the liberties of the black group to always be at least $1$. Therefore, the black group is “living”. Test case 3: A final position that makes the liberties of the black connected component equal to $0$: ```plain @*@@. @***@ **@** *@.@* **@** ***** ``` --- **[Constraints]** **This problem uses bundled testdata.** For $100\%$ of the data: $1 \le n, m \le 2 \times {10}^3$, $1 \le T \le {10}^5$. Each cell of the initial board is either `.` or `*`, and there is at least one `.`, and at least one `*`. **It is guaranteed that black stones are connected.** The sum of $n \times m$ over each test point is at most $4 \times {10}^6$. - Subtask 1 (9 points): $n = 1$. - Subtask 2 (10 points): $n = 2$, $m = 3$. - Subtask 3 (16 points): the number of `.` is at most $7$, $n, m \le 10$, $T \le 50$. - Subtask 4 (24 points): the number of `.` is at most $14$, $n, m \le 10$, $T \le 50$. - Subtask 5 (15 points): $n, m \ge 3$, and all boundary cells of the input position are `.`. That is, $\forall (i, j)$, if $i = 1 \lor i = n \lor j = 1 \lor j = m$, then $(i, j)$ must be empty. - Subtask 6 (26 points): no special constraints. --- --- --- P.S. Froggy and uyom are both (amateur 4-dan brothers who have not played for a long time), feel free to find us and beat us up. Translated by ChatGPT 5