← 返回题目列表

AtCoder · pakencamp_2019_day3_h

H. 保护帕肯王国!

中文机器翻译题面 查看原题

配点: 100 点

問題文

帕肯战争终于开始了!

帕肯战争的战场是 它由N \times N 方块表示。从这战场之上 从左起第 i th,从左边开始 j 广场 我们将其表示为 (i, j) 。

这是帕肯王国的士兵。 M 敌国人民、士兵 M 一个人站着。更具体地说, 当S_{i, j} 是 从 X 当广场 (i, j) 一名来自帕肯王国的士兵站在那里。Q 一名来自敌国的士兵站着。. 是一个空方块。

敌国士兵举枪上下左右斜斜。 您可以向 8 方向拍摄。 (具体如下图)

为了防止敌国士兵能够直接射击帕肯王国的士兵,我们决定在一些方格放置不允许枪支通过的方块。放置方块的条件如下。

  • 这里应该是一个空荡荡的广场,没有帕克王国的士兵,也没有敌国的士兵。

如何使用尽可能少的方块来防止任何敌国的士兵直接射击帕肯王国的士兵。 1 请找到一个。

但是,请注意,此问题的分数是由放置的块数决定的,因此没有必要完全最小化块数。

制約

所有输入数据满足以下约束。

  • N = 100
  • M = 300
  • S_{i, j} 是 Q,X,. 变成
  • S_{i, j} 是 从 Q 的正方形恰好是 M 個
  • S_{i, j} 是 从 X 的正方形恰好是 M 個

关于测试用例生成

帕肯王国的士兵和敌国的士兵的位置几乎是随机生成的,同时满足“帕肯王国的士兵和敌国的士兵永远不会在对角线上相邻”的条件。具体来说, 它是根据单击此处 的生成代码创建的。


得点

提交的分数将按如下方式确定。

  • 用于评分 在 20 测试用例中,1 如果有任何不符合条件的输出(无效格式,允许敌国士兵直接射击巴肯王国士兵的输出), 该点将为0 。
  • 否则,i 测试用例的得分为 a_i 分,提交分数为 floor(\frac{a_{1}+a_{2}+a_{3}+...+a_{20}}{20}) 。

每个测试用例的分数由放置的块数决定。 当 L 时,其定义如下。 当

  • 2 \ 401 \leq L 时,5 点.
  • 1 \ 901 \leq L \leq 2 \ 400 时,14 点.
  • 1 \ 501 \leq L \leq 1 \ 900 时,17 点.
  • 1 \ 201 \leq L \leq 1 \ 500 时,20 点.
  • 1 \ 001 \leq L \leq 1 \ 200 时,23 点.
  • 481 \leq L \leq 1 \ 000 时,50 - (L - 480) \times 0.05 点.
  • 431 \leq L \leq 480 时,100 - (L - 430) \times 1 点.
  • L \leq 430 时,100 点.

入力

输入是按以下格式从标准输入给出的。

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}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, N}
 :  :  :
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}
  • 质量 从 (i, j) ,V_{i, j} = #

此时,请按照以下格式输出您的答案。

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}
V_{3, 1} V_{3, 2} V_{3, 3} \cdots V_{3, N}
 :  :  :
V_{N, 1} V_{N, 2} V_{N, 3} \cdots V_{N, N}

入出力例

例如,请考虑以下输入示例。 (N, M 不满足约束条件,因此不包含在用于评分的数据中。 )

7 3
.Q.....
....X..
.......
.X....Q
.......
Q.....X
.......

在这个输入示例中,当不考虑方块时,战场如下所示:

现在,如果你输出以下内容,你将得到正确的答案。在这种情况下放置的块数 L = 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 满意。