← 返回题目列表

Codeforces · 1450/C2

C2. Errich-Tac-Toe(困难版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是 O 类型的标记不会出现在简单版本的输入中。

Errichto 向 Monogon 提出了以下挑战,以恐吓他不要占据 Codeforces 上的最高贡献者位置。

在 Tic-Tac-Toe 网格中,有 $$$n$$$ 行和 $$$n$$$ 列。网格的每个单元格要么是空的,要么包含一个标记。令牌有两种类型:X和O。如果一行或一列连续存在三个相同类型的令牌,则为获胜配置。否则,它是绘制配置。

第一行的图案是获胜配置。第二行中的图案是绘制配置。

在运算中,您可以将 X 更改为 O,或将 O 更改为 X。令 $$$k$$$ 表示网格中的标记总数。你的任务是在最多$$$\lfloor \frac{k}{3}\rfloor$$$(向下舍入)操作中使网格平局。

您无需最小化操作次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 300$$$) — 网格的大小。

以下 $$$n$$$ 行每行包含一个由 $$$n$$$ 字符组成的字符串,表示初始网格。第 $$$i$$$ 行和 $$$j$$$ 列中的字符是“.”如果单元格为空,或者单元格中的标记类型:“X”或“O”。

保证并非所有单元格都是空的。

所有测试用例的 $$$n$$$ 总和不超过 $$$300$$$。

输出

对于每个测试用例,在应用操作后打印网格的状态。

我们有证据表明解决方案始终存在。如果有多个解决方案,请打印其中一个。

示例

输入 #1

3
3
.O.
OOO
.O.
6
XXXOOO
XXXOOO
XX..OO
OO..XX
OOOXXX
OOOXXX
5
.OOO.
OXXXO
OXXXO
OXXXO
.OOO.

输出 #1

.O.
OXO
.O.
OXXOOX
XOXOXO
XX..OO
OO..XX
OXOXOX
XOOXXO
.OXO.
OOXXO
XXOXX
OXXOO
.OXO.

注意

在第一个测试用例中,第二行第二列最初有三个连续的“O”。通过将中间标记更改为“X”,我们使网格成为平局,并且我们仅更改了 $$$1\le \lfloor 5/3\rfloor$$$ 标记。

在第二个测试用例中,最终的网格是平局。我们只改变了 $$$8\le \lfloor 32/3\rfloor$$$ 代币。

在第三个测试用例中,最终的网格是平局。我们仅更改了 $$$7\le \lfloor 21/3\rfloor$$$ 代币。