← 返回题目列表

Codeforces · 1749/E

E. 仙人掌墙

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

Monocarp 正在玩 Minecraft,想要建造一堵仙人掌墙。他想将其建造在一块大小为 $$$n \times m$$$ 个单元格的沙地上。最初,田野的一些小区里有仙人掌。请注意,在 Minecraft 中,仙人掌不能在彼此相邻的单元格上生长 - 并且初始字段满足此限制。 Monocarp可以种植新的仙人掌(它们也必须满足上述条件)。他无法砍倒地里已经长出的任何仙人掌——他没有斧子,而且仙人掌对他的手来说太刺了。

Monocarp 认为,如果没有从场地顶行到底行的路径,则墙是完整的,这样:

- 路径中每两个连续的单元格相邻;
- 属于该路径的单元格不包含仙人掌。

你的任务是种植最少数量的仙人掌来建造一堵墙(或者报告这是不可能的)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$n \times m \le 4 \cdot 10^5$$$) - 分别是行数和列数。

接下来是 $$$n$$$ 行,如果仙人掌生长在第 $$$i$$$ 行和第 $$$j$$$ 列的交叉处,则 $$$i$$$ 行包含长度为 $$$m$$$ 的字符串 $$$s_i$$$,其中 $$$s_{i, j}$$$ 为“#”。否则,$$$s_{i, j}$$$ 为“.”。

所有测试用例的 $$$n \times m$$$ 总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,如果不可能在不违反规则的情况下建造仙人掌墙,请在第一行打印“NO”。否则,在第一行打印 YES,然后打印 $$$n$$$ 行,每行包含 $$$m$$$ 个字符 — 字段本身,其中第 $$$i$$$ 行的第 $$$j$$$ 字符等于“#”,如果第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点上有仙人掌,否则为“.”。如果有多个最佳答案,请打印其中任何一个。

示例

输入 #1

4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...

输出 #1

YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...