← 返回题目列表

AtCoder · abc445_g

G. 骑士安置

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

分数: 600 点

问题陈述

有一个网格 N 行和 N 列。 牢房位于 i从顶部算起的第行 (1 \le i \le N) 和 j左起第 列 (1 \le j \le N) 称为单元格 (i,j).

每个单元格都是一个空单元格或一个壁单元格,由一系列 N 长度的字符串 N 每个, (S_1,S_2,\ldots,S_N)。 细胞 如果 (i,j)\ (1 \le i \le N,1 \le j \le N) 是一个空单元格 j第一个字符 S_i is .,以及壁细胞(如果是) #.

你想在这个网格上放置尽可能多的棋子。 棋子的放置受到以下限制。

  • 无法将棋子放置在墙单元上。
  • 单个单元格上最多可以放置一块。
  • 如果将一块放在单元格上 (i,j),移动到达的单元格上不能放置任何棋子 A 单元格垂直和 B 单元格水平方向 (i,j),或通过移动到达的单元格 B 单元格垂直和 A 单元格水平排列。更正式地说,如果将一块放在单元格上 (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) (如果这些单元格存在)。

让 K 是在这些约束下可以放置的最大件数,并找到一个放置 K 满足约束条件的件。

约束

  • 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).

输入

输入由标准输入按以下格式给出:

N A B
S_1
S_2
\vdots
S_N

输出

查找以下位置之一 K 满足约束条件的片段,并将其作为字符串输出 N 行。 的 i第行 (1 \le i \le N) 应包含一个字符串 N 字符组成 ., o,和 #。 的 j- 第一个字符 上字符串的 (1 \le j \le N) 上的字符串 i- 第行应该是 . 如果细胞 (i,j) 是一个没有碎片的空单元格, o 如果细胞 (i,j) 是一个带有一块的空单元格,并且 # 如果细胞 (i,j) 是壁细胞。

如果有多个有效展示位置,则其中任何一个都将被接受。


示例输入 1

5 1 2
..#..
..##.
.#..#
##..#
.#...

示例输出 1

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

例如, 10 碎片可以按如下方式放置,同时满足约束。

无法放置 11 块同时满足约束条件,因此输出与上面放置相对应的棋盘,

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

将被判定为正确。

请注意,如果有多个有效位置,则任何有效位置都将被接受。 例如,以下还允许 10 在满足约束的情况下放置的棋子。

因此,输出

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

也将被判断为正确。


示例输入 2

4 0 1
.###
##.#
#.##
###.

示例输出 2

o###
##o#
#o##
###o

可以通过在每个空单元上放置一块来满足约束。


示例输入 3

20 3 4
#...#...........##.#
..##........#.......
.....##..#....###.#.
.#...##.##.#.#.#..#.
#...#.....###..#...#
#...##......##.##.#.
.#....#.##.##...#...
#..##..........#...#
##.#..........##....
...#..#....#.#.#...#
#.....#.##.#...#....
##................#.
.#....#..#....#.....
........#........#.#
........#.#..##....#
.##.....#....#......
.##.#.##....#.#...##
......#...#..#......
.........##...#..#.#
###.....#...#....#..

示例输出 3

#ooo#....ooo....##o#
oo##o...oooo#..ooooo
ooooo##oo#ooo.###o#o
o#ooo##.##o#o#.#oo#o
#ooo#....o###..#ooo#
#...##...oo.##.##o#.
.#o...#.##.##...#oo.
#.o##.....o....#..o#
##o#.....o.o..##oo..
ooo#oo#.ooo#.#.#ooo#
#oooo.#o##o#oo.#oooo
##ooo...oooo..o.oo#o
.#oo..#o.#oo..#oooo.
........#.o......#o#
..oo....#.#o.##..o.#
.##.o...#.o..#....o.
.##o#.##...o#.#.oo##
oooooo#.oo#oo#o.oooo
.oooo..o.##ooo#oo#o#
###oooo.#ooo#.o.o#oo