← 返回题目列表

Codeforces · 1450/C1

C1. 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”。

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

在简单版本中,字符“O”不会出现在输入中。

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

输出

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

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

示例

输入 #1

3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..

输出 #1

.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..

注意

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

在第二个测试用例中,我们仅更改 $$$9\le \lfloor 32/3\rfloor$$$ 标记,并且行或列中不存在任何三个连续的“X”或“O”,因此是平局。

在第三个测试用例中,我们仅更改 $$$3\le \lfloor 12/3\rfloor$$$ 标记,结果网格是平局。