P14689 [ICPC 2025 Yokohama R] ICPC Board

作为一名考古学家，你在一个古城的遗址中发现了一块长方形的木制板。木板被划分为一个网格，每个网格单元格最初似乎都刻有字母 'C'、'I' 或 'P' 中的一个。然而，由于年代久远，部分字母现已无法辨识。 在你的调查过程中，你提出了以下假设：木板上任何一个 $2 \times 2$ 的方格原本都包含两个 'C'、一个 'I' 和一个 'P'。 你现在想检验这个假设是否与已发现的木板相符。如果相符，请展示一种符合该假设的原始字母排列的可能性。

输入包含一个或多个测试用例。输入的第一行包含一个整数 $t$ ($1 \le t \le 500$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个用例的格式如下。 $$ n\ m $$ $$ c_{1,1}\ c_{1,2}\ \cdots\ c_{1,m} $$ $$ c_{2,1}\ c_{2,2}\ \cdots\ c_{2,m} $$ $$ \vdots $$ $$ c_{n,1}\ c_{n,2}\ \cdots\ c_{n,m} $$ 一个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1000$, $2 \le m \le 1000$)。它们分别表示木板的行数和列数。接下来的 $n$ 行，每行包含 $m$ 个字符，描述了已发现的木板。第 $i$ 行的第 $j$ 个字符 $c_{i,j}$ 是 'C'、'I'、'P' 或 '?' 中的一个。如果 $c_{i,j}$ 是 'C'、'I' 或 'P'，则表示第 $i$ 行第 $j$ 列的单元格可以识别为刻有该字母。如果 $c_{i,j}$ 是 '?'，则表示该单元格的字母无法辨识。 所有测试用例的 $n$ 之和不超过 $1000$。$m$ 也满足相同条件。

对于每个测试用例，如果该假设与已发现的木板不符，则单独输出一行 $no$。否则，第一行输出 $yes$，然后输出 $n$ 行，表示一种符合该假设的原始字母排列的可能性。这 $n$ 行中的每一行应包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符应为第 $i$ 行第 $j$ 列单元格中的字母。如果有多种可能的排列，你可以输出其中任意一种。

翻译由 DeepSeek V3 完成