/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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) は S _ i の j 文字目が . のとき空きマスであり、# のとき壁マスです。
あなたは、このマス目にコマを置けるだけ置きたいです。 コマの置き方には以下のような制約があります。
- 壁マスにコマを置くことはできない。
- 1 つのマスにコマを 2 つ以上置くことはできない。
- マス (i,j) にコマが置かれているとき、マス (i,j) から縦に A マス横に B マス移動したマスおよび、縦に 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\le300
- 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) には、., o, # からなる N 文字の文字列を出力せよ。
i 行目に出力する文字列の j 文字目 (1\le j\le N) は、マス (i,j) がコマが置かれていない空きマスなら . 、マス (i,j) がコマが置かれている空きマスなら o 、マス (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
すべての空きマスに 1 つずつコマを置くことで制約を満たすことができます。
入力例 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
Score : 600 points
Problem Statement
There is a grid with N rows and N columns. The cell at the i-th row from the top (1 \le i \le N) and the j-th column from the left (1 \le j \le N) is called cell (i,j).
Each cell is an empty cell or a wall cell, represented by a sequence of N strings of length N each, (S_1,S_2,\ldots,S_N).
Cell (i,j)\ (1 \le i \le N,1 \le j \le N) is an empty cell if the j-th character of S_i is ., and a wall cell if it is #.
You want to place as many pieces as possible on this grid. The placement of pieces is subject to the following constraints.
- A piece cannot be placed on a wall cell.
- At most one piece can be placed on a single cell.
- If a piece is placed on cell (i,j), no piece can be placed on the cell reached by moving A cells vertically and B cells horizontally from cell (i,j), or the cell reached by moving B cells vertically and A cells horizontally. More formally, if a piece is placed on cell (i,j), then no piece can be placed on any of cell (i+A,j+B), cell (i+B,j+A), cell (i+B,j-A), cell (i+A,j-B), cell (i-A,j-B), cell (i-B,j-A), cell (i-B,j+A), cell (i-A,j+B) (if those cells exist).
Let K be the maximum number of pieces that can be placed under these constraints, and find one placement of K pieces satisfying the constraints.
Constraints
- 1 \le N \le 300
- 0 \le A \le B \le N
- 1 \le B
- N,A,B are integers.
- S_i is a string of length N consisting of
.and#(1 \le i \le N).
Input
The input is given from Standard Input in the following format:
N A B S_1 S_2 \vdots S_N
Output
Find one placement of K pieces satisfying the constraints, and output it as strings over N lines.
The i-th line (1 \le i \le N) should contain a string of N characters consisting of ., o, and #.
The j-th character (1 \le j \le N) of the string on the i-th line should be . if cell (i,j) is an empty cell with no piece, o if cell (i,j) is an empty cell with a piece, and # if cell (i,j) is a wall cell.
If there are multiple valid placements, any of them will be accepted.
Sample Input 1
5 1 2 ..#.. ..##. .#..# ##..# .#...
Sample Output 1
o.#.o oo##. o#..# ##.o# o#ooo
For example, 10 pieces can be placed as follows while satisfying the constraints.
It is impossible to place 11 pieces while satisfying the constraints, so outputting the board corresponding to the placement above,
o.#.o oo##. o#..# ##.o# o#ooo
will be judged as correct.
Note that any valid placement will be accepted if there are multiple of them. For example, the following also allows 10 pieces to be placed while satisfying the constraints.
Thus, outputting
oo#oo o.##o .#..# ##..# o#ooo
will also be judged as correct.
Sample Input 2
4 0 1 .### ##.# #.## ###.
Sample Output 2
o### ##o# #o## ###o
The constraints can be satisfied by placing one piece on each empty cell.
Sample Input 3
20 3 4 #...#...........##.# ..##........#....... .....##..#....###.#. .#...##.##.#.#.#..#. #...#.....###..#...# #...##......##.##.#. .#....#.##.##...#... #..##..........#...# ##.#..........##.... ...#..#....#.#.#...# #.....#.##.#...#.... ##................#. .#....#..#....#..... ........#........#.# ........#.#..##....# .##.....#....#...... .##.#.##....#.#...## ......#...#..#...... .........##...#..#.# ###.....#...#....#..
Sample Output 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