P13114 [GCJ 2019 #1C] Bacterial Tactics

Becca 和 Terry 是微生物学家，他们之间有着友好的竞争。当他们需要从研究中休息时，会一起玩一个游戏。该游戏在一个由 $\mathbf{R}$ 行 $\mathbf{C}$ 列组成的单元格矩阵上进行。最初，每个格子要么是空的，要么含有放射性物质。 每位玩家轮流行动，如果矩阵中没有空格子，则该玩家输掉游戏。否则，玩家选择一个空格子并在其中放置一个细菌菌落。细菌菌落有两种类型：H（代表“水平”）和 V（代表“垂直”）。 - 当在一个空格子中放置 H 型菌落时，它会占据该格子（使其变为非空），并尝试向西边（如果有）和东边（如果有）的相邻格子扩散。 - 当在一个空格子中放置 V 型菌落时，它会占据该格子（使其变为非空），并尝试向南边（如果有）和北边（如果有）的相邻格子扩散。 每当菌落（无论哪种类型）尝试扩散到某个格子时： - 如果该格子含有放射性物质，菌落发生变异，放置该菌落的玩家输掉游戏。 - 如果该格子为空，菌落占据该格子（使其变为非空），然后再次触发上述规则（即菌落会继续尝试扩散）。 - 如果该格子已经含有细菌（任意类型），菌落不会扩散到该格子。 注意，可能存在玩家所有可选的行动都会导致自己输掉游戏的情况，因此该玩家注定失败。下面的样例解释中有关于游戏玩法的示例。 Becca 先手，然后两位玩家轮流行动，直到其中一方输掉游戏。如果双方都采取最优策略，谁会获胜？如果 Becca 会获胜，她有多少种不同的必胜开局？（只有当使用的格子不同，或菌落类型不同，或两者都不同，两个开局才算作不同。）

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组数据的第一行为两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，分别表示矩阵的行数和列数。接下来有 $\mathbf{R}$ 行，每行有 $\mathbf{C}$ 个字符。第 $i$ 行第 $j$ 个字符表示矩阵第 $i$ 行第 $j$ 列的格子。每个字符要么是 .（空格子），要么是 #（含有放射性物质的格子）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个整数：如果 Becca 无法获胜，则为 0；如果 Becca 能获胜，则为她拥有的不同必胜开局数量，如上所述。

**样例解释** 在样例 1 中，Becca 不能在西南角的空格子放置 H 型菌落，也不能在东北角的空格子放置 V 型菌落，因为那样会扩散到放射性格子，Becca 会输。她只有两种不会立即输掉的策略： 1. 在西北角或东北角的空格子放置 H 型菌落。该菌落还会扩散到另一个角的空格子。 2. 在西北角或西南角的空格子放置 V 型菌落。该菌落还会扩散到另一个角的空格子。 如果 Becca 选择策略 1，Terry 可以在西南角的空格子放置 V 型菌落。如果 Becca 选择策略 2，Terry 可以在东北角的空格子放置 H 型菌落。无论哪种情况，Becca 下一轮都没有空格可选，因此她会输，Terry 获胜。 在样例 2 中，Becca 的任何开局都会导致变异。 在样例 3 中，Becca 有 5 种可能的开局会导致变异，但另外 7 种是必胜的。她可以在第二行的任意格子放置 H 型菌落，或者在第二列的任意格子放置 V 型菌落。无论哪种情况，她都会留下两个不相连的 1 或 2 个格子的集合。在每个集合中，只能放置一种类型的菌落，且放置后会消耗掉该集合内所有空格。因此，无论 Terry 选择消耗哪一个集合，Becca 都可以消耗另一个集合，使 Terry 无法行动。 在样例 4 中，Becca 的两种不同开局都是必胜的。 在样例 5 中，Becca 没有可行的开局。 **数据范围** $1 \leq \mathbf{T} \leq 100$。 **测试点 1（可见）** - $1 \leq \mathbf{R} \leq 4$。 - $1 \leq \mathbf{C} \leq 4$。 **测试点 2（隐藏）** - $1 \leq \mathbf{R} \leq 15$。 - $1 \leq \mathbf{C} \leq 15$。 由 ChatGPT 4.1 翻译