P16855 [GKS 2021 #E] Palindromic Crossword

填字游戏是一个由黑色单元格和字母 A-Z 组成的矩形网格，如下图所示。 :::align{center}  ::: 填字游戏中的单词定义为最长的垂直或水平字符段。在下方的填字游戏中，`DO` 和 `ON` 是单词的例子。 :::align{center}  ::: 一个**回文填字游戏**是指其中每个单词都是回文。记 $R_{i,j}$ 为第 $i$ 行第 $j$ 列的字符，$i$ 和 $j$ 均从 $1$ 开始编号。左上角为 $R_{1,1}$。在下面的回文填字游戏示例中，位于 $R_{3,2}$ 的 `B` 既属于从 $R_{3,1}$ 开始的水平单词，也属于结束于 $R_{4,2}$ 的垂直单词，且这两个单词都是回文。 :::align{center}  ::: 你被赠予了一个有 $N$ 行 $M$ 列的回文填字游戏。你完成了填字游戏，扔掉了线索，准备把它挂在墙上。然而，你不小心擦掉了一些字母！你想尽可能地恢复填字游戏，但你已经没有线索了。仅利用填字游戏是回文的这一知识，恢复给定填字游戏中尽可能多的缺失字符。 缺失的字母在下图中表示为空的白色单元格。左侧的填字游戏是你得到的，右侧的填字游戏是你在恢复了尽可能多的字母后的结果。剩余的单元格无法填充，因为我们没有足够的信息来恢复它们。 :::align{center}  :::

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，分别表示填字游戏的行数和列数。 接下来的 $N$ 行表示网格的 $N$ 行。第 $i$ 行由 $M$ 个字符组成，表示 $R_{i,1}, R_{i,2}, \dots, R_{i,M}$。每个字符是以下之一： - 大写字母（A-Z） - 句点（`.`）表示缺失的字母（在示例填字游戏中为空的白色单元格） - 井号（`#`）表示黑色单元格

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是被填充的空白色单元格的数量。然后，输出 $N$ 行，表示最终的网格，其中缺失的字符（`.`）在可能的情况下被替换为大写字母（A-Z）。

在样例 #2 中，我们可以填充 $8$ 个空白。填充缺失字母的方式如下： - 第 $1$ 行第 $4$ 列：由第 $1$ 行第 $1$ 列的字符可知为 `A`。 - 第 $2$ 行第 $4$ 列 = 第 $1$ 行第 $4$ 列的 `A`。 - 第 $2$ 行第 $6$ 列 = 第 $2$ 行第 $4$ 列的 `A`。 - 第 $3$ 行第 $6$ 列 = 第 $2$ 行第 $6$ 列的 `A`。 - 第 $3$ 行第 $2$ 列 = 第 $3$ 行第 $1$ 列的 `B`。 - 第 $4$ 行第 $2$ 列 = 第 $3$ 行第 $2$ 列的 `B`。 - 第 $4$ 行第 $3$ 列 = 第 $4$ 行第 $2$ 列的 `B`。 - 第 $4$ 行第 $4$ 列 = 第 $4$ 行第 $1$ 列的 `A`。 ### 限制条件 $1 \le T \le 100$。 至少存在一种填充方式，使得给定的输入网格成为回文填字游戏。 网格中的所有字符均属于集合 $\{\texttt{A-Z}, \#, .\}$。 **测试集 1** $1 \le N, M \le 50$。 **测试集 2** 最多 $10$ 个测试用例满足： $1 \le N, M \le 1000$。 其余测试用例满足： $1 \le N, M \le 50$。 翻译由 DeepSeek V4 Pro 完成