AT_pakencamp_2019_day3_h パ研王国を守れ！

帕研战争终于打响了！ 战场可以用一个 $N \times N$ 的网格表示。网格中的每个格子用 $(i, j)$ 来标识，表示这是第 $i$ 行、第 $j$ 列的格子。 在这个战场上有 $M$ 名帕研王国的士兵和 $M$ 名敌国的士兵。具体情况如下：如果格子 $S_{i,j}$ 是 `X`，表示那里有帕研王国的士兵；如果是 `Q`，则表示有敌国的士兵；若是 `.`，则表示格子是空的。 敌国的士兵可以朝八个方向射击：上下左右以及对角线方向。（如下图所示）  为了阻止敌国士兵直接射击到帕研王国的士兵，我们计划在一些空格上放置障碍物。放置障碍物的条件是： - 格子上必须没有帕研王国的士兵或敌国的士兵，并且该格子是空的。 请尽可能使用最少的障碍物，保证敌国的士兵无法直接射击到帕研王国的任何士兵。 需注意的是，放置多少个障碍物会影响得分，所以不需要完全做到使用最少的障碍物。

输入通过标准输入给出： > $N$ $M$ > $S_{1, 1}\ S_{1, 2}\ S_{1, 3}\ \cdots\ S_{1, N}$ > $S_{2, 1}\ S_{2, 2}\ S_{2, 3}\ \cdots\ S_{2, N}$ > $\vdots$ > $S_{N, 1}\ S_{N, 2}\ S_{N, 3}\ \cdots\ S_{N, N}$

输出中每个格子 $(i, j)$ 的状态用 $V_{i, j}$ 表示，具体规则如下： - 如果格子 $(i, j)$ 上没有放置障碍物，令 $V_{i, j} = S_{i, j}$ - 如果该格子上放置了障碍物，则 $V_{i, j} = \texttt{\#}$ 请按照以下格式输出： > $V_{1, 1}\ V_{1, 2}\ V_{1, 3}\ \cdots\ V_{1, N}$ > $V_{2, 1}\ V_{2, 2}\ V_{2, 3}\ \cdots\ V_{2, N}$ > $\vdots$ > $V_{N, 1}\ V_{N, 2}\ V_{N, 3}\ \cdots\ V_{N, N}$

### 约束 所有输入数据需满足以下条件： - $N = 100$ - $M = 300$ - $S_{i, j}$ 可以是 `Q`，`X` 或 `.` 中之一 - 格子中有且只有 $M$ 个 `Q` - 格子中有且只有 $M$ 个 `X` ### 测试数据生成说明 帕研王国和敌国士兵的位置被设置为“帕研王国与敌国士兵不会相邻”的条件下生成，基本是随机的。具体的生成代码可以查看[这里](https://img.atcoder.jp/pakencamp-2019-day3/0c92256d19fa24d950ffeb3756ba9876.zip)。 ### 得分规则 提交的得分计算如下： - 对于20个测试用例，如果有任意一个结果不满足条件（格式错误或敌国士兵可直接攻击帕研王国士兵），则得分为0。 - 否则，第 $i$ 个测试用例得分为 $a_i$，总得分为 $\lfloor \frac{a_1 + a_2 + \cdots + a_{20}}{20} \rfloor$。 每个测试用例得分基于障碍物数量 $L$ 计算： - 当 $2401 \leq L$ 时，得5分。 - 当 $1901 \leq L \leq 2400$ 时，得14分。 - 当 $1501 \leq L \leq 1900$ 时，得17分。 - 当 $1201 \leq L \leq 1500$ 时，得20分。 - 当 $1001 \leq L \leq 1200$ 时，得23分。 - 当 $481 \leq L \leq 1000$ 时，得 $50 - (L - 480) \times 0.05$ 分。 - 当 $431 \leq L \leq 480$ 时，得 $100 - (L - 430) \times 1$ 分。 - 当 $L \leq 430$ 时，得100分。  ### 输入输出示例 例如，以下输入示例考虑的是： ``` 7 3 .Q..... ....X.. ....... .X....Q ....... Q.....X ....... ``` 对于这个输入例子，如果不放置障碍物，战场会像下图这样：  这是一个正确的输出示例，使用了6个障碍物（对应图A）： ``` .Q..... .#..X.. ...#.#. .X..#.Q ......# Q..#..X ....... ``` 而下面的输出是不正确的，因为第 $(1, 2)$ 位上的敌国士兵可以射击到第 $(4, 2)$ 位的帕研王国士兵。 ``` .Q..... ....X.. ....##. .X..##Q ####### Q...##X ....##. ```  需要注意的是，上述例子不符合 $N = 100$ 和 $M = 300$ 的条件，因此不在评分范围内。所有用于测试的数据中都满足 $N = 100$，$M = 300$。 **本翻译由 AI 自动生成**