题目描述
知名线下真人枪战赛事 Counter Fire World Final 目前正在下北泽举行。
所有参赛选手会在一张**无限大小的网格图**内进行比赛,但初始时的位置会落在一个大小为 $n \times m$ 的矩形区域内,并且每个位置一开始最多只会有一位选手存在。
赛内共设置了 $26$ 个阵营,以 $\text{A},\text{B},\cdots,\text{Z}$ 进行标识。每位选手在比赛开始前会被随机分配到一个阵营中。
作为本场赛事的主办方,你需要在**比赛开始时**对场上局势进行解说。你打算按照以下方案判断局势走向:
- 对每位选手单独进行判断,并假定除了该选手以外,其它选手所处的位置并不会发生变化;
- 当前选手每次只能够选择走到相邻的四个网格(上、下、左、右)中的任意一个;
- 如果下一个网格为空位置,或者存在的选手归属于己方阵营,那么当前选手便可以走到该网格内;
- 如果当前选手被**非己方阵营**的其它选手所包围(即能够行走的网格总数有限),便认定该选手**一定**会在未来的某一时刻被淘汰,否则认为该选手有可能存活到最后。
试判断在所有出现过的阵营中,有哪些阵营到最后可能还会有至少一名选手未被淘汰,又有哪些阵营会被完全淘汰?
输入格式
第一行包含一个正整数 $T$ $(1 \le T \le 10000)$,表示数据组数。
对于每组数据,第一行包含两个正整数 $n,m$ $(3 \le n,m \le 1000)$,表示初始矩形区域的长和宽。其后 $n$ 行,每行包含 $m$ 个字符,表示矩形区域内的选手及其阵营分布。数据保证字符仅由大写字母以及 `.` 组成,其中 `.` 表示空位置。
数据保证 $\sum\limits n\times m \le 10^6$.
输出格式
对于每组数据,在一行内按 `win / lose` 格式输出答案,其中 `win` 表示有哪些阵营到最后可能还会有至少一名选手未被淘汰,`lose` 表示有哪些阵营会被完全淘汰,均按照字典序升序输出。如果 `win` 或 `lose` 内无内容,请用 `-` 代替。
样例输入 #1
5
3 3
.A.
ABA
.A.
3 3
.A.
BCD
.E.
4 5
..AA.
.ABAA
.ABBB
.AAAA
4 5
..AA.
.ABA.
.ABBA
.AAAA
4 5
B.AA.
.ABA.
.ABBA
.AAAA
样例输出 #1
A / B
ABDE / C
AB / -
A / B
AB / -
提示
对于样例一:`B` 阵营选手被 `A` 阵营选手完全包围而淘汰。
对于样例二:`C` 阵营选手被 `ABDE` 阵营选手完全包围而淘汰。
对于样例三:`B` 阵营选手未被 `A` 阵营选手完全包围,故该阵营可能存活。
对于样例五:位于 $(1,1)$ 位置的 `B` 阵营选手可能存活,因此即使 `B` 阵营的其余选手因被包围而淘汰,该阵营也有可能存活到最后。
来源
2023-05 多校联合训练 ZJNU站 正式赛