骑士放置AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)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)$.
有一个 $N$ 行 $N$ 列的网格。从上往下数第 $i$ 行 $(1 \le i \le N)$、从左往右数第 $j$ 列 $(1 \le j \le N)$ 的格子称为格子 $(i,j)$。AI (CI翻译)
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 #.
给定由 $N$ 个长度均为 $N$ 的字符串 $(S_1,S_2,\ldots,S_N)$ 表示的网格，其中每个格子为空地或墙壁。若 $S_i$ 的第 $j$ 个字符为 .，则格子 $(i,j)\ (1 \le i \le N,1 \le j \le N)$ 为空地；若该字符为 #，则格子 $(i,j)$ 为墙壁。AI (CI翻译)
You want to place as many pieces as possible on this grid. The placement of pieces is subject to the following constraints.
你希望在这个网格上放置尽可能多的棋子。棋子的放置需要满足以下条件。AI (CI翻译)
- 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).
- 不能在墙壁上放置棋子。
- 每个格子至多放置一个棋子。
- 如果在格子
$(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)$。
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.
设在满足上述条件的情况下最多可以放置 $K$ 个棋子，请找出一种放置 $K$ 个棋子的方案。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$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)$.
$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)$。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N A B
S_1
S_2
\vdots
S_NN A B
S_1
S_2
\vdots
S_NOutput
输出格式
AI (CI翻译)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.
请找出一种满足条件的 $K$ 个棋子的放置方案，并按 $N$ 行输出字符串。第 $i$ 行 $(1 \le i \le N)$ 应包含一个由 ., o 和 # 组成的长度为 $N$ 的字符串。第 $i$ 行字符串的第 $j$ 个字符 $(1 \le j \le N)$ 应为：如果格子 $(i,j)$ 是没有放置棋子的空地，则为 .；如果格子 $(i,j)$ 是放置了棋子的空地，则为 o；如果格子 $(i,j)$ 是墙壁，则为 #。AI (CI翻译)
If there are multiple valid placements, any of them will be accepted.
如果存在多种满足条件的放置方案，输出其中任意一种即可。AI (CI翻译)
样例
5 1 2
..#..
..##.
.#..#
##..#
.#...
o.#.o
oo##.
o#..#
##.o#
o#ooo
4 0 1
.###
##.#
#.##
###.
o###
##o#
#o##
###o
20 3 4
#...#...........##.#
..##........#.......
.....##..#....###.#.
.#...##.##.#.#.#..#.
#...#.....###..#...#
#...##......##.##.#.
.#....#.##.##...#...
#..##..........#...#
##.#..........##....
...#..#....#.#.#...#
#.....#.##.#...#....
##................#.
.#....#..#....#.....
........#........#.#
........#.#..##....#
.##.....#....#......
.##.#.##....#.#...##
......#...#..#......
.........##...#..#.#
###.....#...#....#..
#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
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。