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 翻译