P13148 [GCJ 2018 #2] Gridception
题目描述
盗贼大师 Jom Codd 能够潜入他人的梦境。由于梦境观察技术还不够先进，Codd 看到的梦境是一个由单元格组成的梦境网格，每个单元格要么是白色，要么是黑色。
给定一个初始的梦境网格，Codd 可以通过“深入”操作，将每个白色单元格替换为一个 $2\times 2$ 的白色单元格网格，每个黑色单元格替换为一个 $2\times 2$ 的黑色单元格网格；这样会生成一个面积扩大四倍的新梦境网格。他可以在此基础上继续深入，如此反复。例如，给定如下初始梦境网格：
```
BBB
BWB
BBB
```
深入一次后，得到的新梦境网格为：
```
BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB
```
再深入一次，得到的新梦境网格为：
```
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
```
以此类推。
Codd 刚刚潜入了一个梦境，并看到了它的初始梦境网格。他正执行一项极其艰难的任务，他知道自己需要多次深入。为了帮助自己导航，他正在观察初始梦境网格中的各种“模式”。一个模式由一组通过边相连（仅共享角不算相连）的单元格及其颜色组成。一个模式可以包含内部空洞（只要模式的单元格是一个连通块）；这些空洞不算作模式的一部分。如果两个模式的单元格数量和排列方式完全相同（不允许翻转或旋转），且颜色一致，则认为它们是相同的模式。
例如，在上述网格中，以下 $8$ 个单元格的模式出现在初始网格中：
```
BBB
B B
BBB
```
在深入一次后，这个模式不再出现，但在深入两次、三次及之后的每一次深入的梦境网格中，这个模式都会出现。
Codd 想要找到初始梦境网格中，能够在至少 $10^{100}$ 个更深层梦境网格中出现的最大模式。对于给定的例子，上述模式就是最大的满足条件的模式。尽管它在深入一次后没有出现，但在至少 $10^{100}$ 个更深层网格中都会出现。其他更小的模式也满足条件，但不存在 $9$ 个单元格的模式满足条件；唯一可能的 $9$ 个单元格模式只能是整个初始梦境网格，但这个模式在任何更深层网格中都不会出现，更不用说出现 $10^{100}$ 次了。
输入格式
第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组数据第一行包含两个整数 $R$ 和 $C$，分别表示梦境网格的行数和列数。接下来的 $R$ 行，每行包含 $C$ 个字符，每个字符为 `B` 或 `W`，直接表示梦境网格。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足 Codd 要求的最大模式的大小。
说明/提示
**样例解释**
样例 1 即为题目描述中的例子。
样例 2 中，一个可能的最大模式为：
```
BBB
WB
```
另一个同样大小的模式为：
```
BBB
W W
```
样例 3 中，整个初始梦境网格就是最大的模式。
样例 4 中，注意五个 W 不能构成一个合法模式，因为它们不是连通的。然而，以下模式是一个最大模式：
```
WB
BW
```
样例 5 中，整个初始梦境网格就是最大的模式。需要注意的是，尽管这个网格恰好是从 BW 深入得到的，但这与本题无关；Codd 永远不会“向上回溯”。
**数据范围**
- $1 \leq T \leq 100$。
**测试点 1（10 分，公开）**
- $1 \leq R \leq 3$。
- $1 \leq C \leq 4$。
**测试点 2（22 分，隐藏）**
- $1 \leq R \leq 20$。
- $1 \leq C \leq 20$。
由 ChatGPT 4.1 翻译