CF1450C2 Errich-Tac-Toe (Hard Version)

简单版与困难版的唯一区别在于，简单版的输入中不会出现 O 类型的棋子。 Errichto 给了 Monogon 如下挑战，以此来威慑他不要夺走他在 Codeforces 上的顶级贡献者位置。 在一个井字棋棋盘上，有 $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$。

对于每个测试用例，输出操作后的棋盘状态。 我们有证明表明解一定存在。如果有多种方案，输出任意一种即可。

在第一个测试用例中，第二行和第二列最初各有三个连续的 'O'。将中间的棋子改为 'X' 后，棋盘变为平局局面，只改变了 $1\le \lfloor 5/3\rfloor$ 个棋子。 在第二个测试用例中，最终棋盘为平局局面，只改变了 $8\le \lfloor 32/3\rfloor$ 个棋子。 在第三个测试用例中，最终棋盘为平局局面，只改变了 $7\le \lfloor 21/3\rfloor$ 个棋子。 由 ChatGPT 4.1 翻译