AT_abc445_g.[ABC445G] Knight Placement

在一个有 $N$ 行 $N$ 列的网格上，第 $i$ 行（自上而下）第 $j$ 列（自左而右）的格子称为格子 $(i, j)$，其中 $1 \le i \le N, 1 \le j \le N$。

每个格子要么是空格子，要么是墙格子。整个网格由 $N$ 个长度为 $N$ 的字符串 $(S_1, S_2, \ldots, S_N)$ 表示。如果 $S_i$ 的第 $j$ 个字符是 .，则 $(i, j)$ 是空格子；如果是 #，则是墙格子。

你想在这个网格上尽可能多地放置棋子，放棋子需要满足以下约束：

• 棋子不能放在墙格子上。
• 每个格子最多只能放一个棋子。
• 如果在 $(i, j)$ 放了一个棋子，那么对于如下八个相对位置的格子，不允许再放下棋子（如果这些格子在网格范围内）：$(i+A, j+B)$、$(i+B, j+A)$、$(i+B, j-A)$、$(i+A, j-B)$、$(i-A, j-B)$、$(i-B, j-A)$、$(i-B, j+A)$、$(i-A, j+B)$。也就是说，从当前格子竖直走 $A$ 个单元、水平走 $B$ 个单元，或交换 $A$ 和 $B$ 的走法（正负方向）到达的格子，都不能再放置棋子。

设 $K$ 为在上述约束条件下能放置的最大棋子数。请找出一种合法的放置方案，使得能放 $K$ 个棋子。

输入按以下格式从标准输入读入：

$N\ A\ B$
$S_1$
$S_2$
$\vdots$
$S_N$

请输出一种满足约束条件并放置了 $K$ 个棋子的方案。输出共 $N$ 行，第 $i$ 行（$1 \le i \le N$）为一个长度为 $N$ 的字符串，只含有 ., o, #。

• 如果第 $i$ 行第 $j$ 列是空格子并且没有棋子，输出 .。
• 如果该格子是空格子且有棋子，输出 o。
• 如果该格子是墙格子，输出 #。

如果有多种方案，输出任意一种都可以。

样例解释 1

例如，可以按如下方式放置 $10$ 个棋子，并满足所有条件：

不能再放下第 $11$ 个棋子了。

所以上述布局对应的输出：

o.#.o
oo##.
o#..#
##.o#
o#ooo

也是合法答案。

注意，如果有多种方案，任意方案都可以。例如，下面也是 $10$ 个棋子的方案：

输出：

oo#oo
o.##o
.#..#
##..#
o#ooo

同样被判为正确。

样例解释 2

对于该情况，可以在每个空格子上都放一个棋子，并满足所有条件。

数据范围

• $1 \le N \le 300$
• $0 \le A \le B \le N$
• $1 \le B$
• $N, A, B$ 为整数
• $S_i$ 为长度为 $N$ 仅由 . 和 # 组成的字符串（$1 \le i \le N$）

由 ChatGPT 5 翻译