P13161 [GCJ 2017 Qualification] Fashion Show

你即将举办一场时装秀，展示三种新款服装。秀场的舞台是最时尚的形状：一个 $N \times N$ 的网格。 网格中的每个格子可以是空的（用 `.` 表示），也可以有一位时装模特。模特分为三种类型，取决于他们所穿的服装风格：`+`、`x`，以及超级时尚的 `o`。一个格子中如果有 `+` 或 `x` 型模特，将为秀场增加 1 分风格分；如果有 `o` 型模特，则增加 2 分风格分。空格子不加分。 为了达到最佳艺术效果，模特的摆放有如下规则： - 只要有两个模特处于同一行或同一列，这两个模特中至少有一个必须是 `+`。 - 只要有两个模特处于同一对角线，这两个模特中至少有一个必须是 `x`。 形式化地说，若一个模特位于第 $i_0$ 行第 $j_0$ 列，另一个模特位于第 $i_1$ 行第 $j_1$ 列，则当 $i_0 = i_1$ 时他们同一行，当 $j_0 = j_1$ 时同一列，当 $i_0 + j_0 = i_1 + j_1$ 或 $i_0 - j_0 = i_1 - j_1$ 时同一对角线。 例如，下面这个网格是不合法的： ``` ... x+o .+. ``` 中间一行有一对模特（`x` 和 `o`），但其中没有 `+`。从底行的 `+` 到中间行的 `o` 的对角线上有两个模特，但都不是 `x`。 而下面这个网格是合法的，没有任何行、列或对角线违反规则： ``` +.x +x+ o.. ``` 你的艺术顾问已经按照规则在某些格子中预先放置了 $M$ 个模特。你可以在任意数量（包括零个）格子中自由添加任意类型的模特。你不能移除已有的模特，但可以将已有的 `+` 或 `x` 型模特升级为 `o` 型，只要不违反上述规则。 你的任务是找到一种合法的放置和/或升级方式，使得获得的风格分最大。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据的第一行包含两个整数 $N$ 和 $M$。接下来 $M$ 行，每行包含一个字符（`+`、`x` 或 `o`）和两个整数 $R_i$、$C_i$，表示该模特的类型和位置。网格的行从上到下编号为 $1$ 到 $N$，列从左到右编号为 $1$ 到 $N$。

对于每个测试用例，首先输出一行 `Case #x: y z`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你安排下获得的风格分，$z$ 是你添加和/或替换的模特总数。然后，对于每一个你添加或替换的模特，输出一行，格式与输入部分相同，字符为你添加或替换的模特类型。这 $z$ 行顺序不限。 如果有多种合法方案，你可以输出其中任意一种。

**样例说明** 样例输出展示了样例数据的一组解。其他解也是可能的。注意最后一个样例不会出现在 Small 数据集中。 在样例 1 中，网格为 $2 \times 2$，初始为空。输出对应如下网格（用 `.` 表示空格）： ``` x. +o ``` 在样例 2 中，唯一的格子已经被 `o` 型模特占据，无法再添加或替换模特。 在样例 3 中，初始网格如下： ``` ... +++ x.. ``` 输出对应如下网格： ``` .x. ++o x.. ``` **数据范围** - $1 \leq T \leq 100$。 - $1 \leq N \leq 100$。 - $1 \leq C_i \leq N$，对所有 $i$。 - $0 \leq M \leq N^2$。 - 不会有两个预放置的模特在同一格子。 - 保证所有预放置的模特均符合规则。 **小数据（10 分，测试集 1 - 可见）** - $R_i = 1$，对所有 $i$。（所有预放置的模特都在第一行。你可以在该行添加/替换模特，也可以在其他行添加模特。） **大数据（25 分，测试集 2 - 隐藏）** - $1 \leq R_i \leq N$，对所有 $i$。 由 ChatGPT 4.1 翻译