分数: 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