← 返回题目列表

AtCoder · agc004_c

C. 和网格

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

分数: 700 点

问题陈述

Snuke和Ciel去了一家奇怪的文具店。他们每人都有一张透明方格纸,上面写着 H 行和 W 列。

Snuke 在他的论文中将一些细胞涂成红色。在这里,涂成红色的单元格是 4-连接,也就是说,通过仅移动到垂直或水平相邻的红细胞,可以从任何红细胞遍历到任何其他红细胞。

Ciel 在她的论文中将一些细胞涂成蓝色。在这里,涂成蓝色的细胞是 4 连接的。

随后,他们将两张纸以相同的方向精确地重叠在一起。然后,红细胞和蓝细胞的交汇处呈现出紫色。

给你一个字母矩阵 a_{ij} (1≤i≤H, 1≤j≤W)描述紫色单元格的位置。如果单元格位于 i第行和 j第-列是紫色的,那么 a_{ij} is #,否则 a_{ij} is .。在此,可以保证 最外面的单元格没有是紫色的。也就是说,如果 i=1, H or j = 1, W,那么 a_{ij} is ..

找到一对与所描述的情况一致的红细胞和蓝细胞的位置集合。可以证明,解总是存在的。

约束

  • 3≤H,W≤500
  • a_{ij} is # or ..
  • If i=1,H or j=1,W,那么 a_{ij} is ..
  • 至少其中之一 a_{ij} is #.

输入

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

H W
a_{11}...a_{1W}
:
a_{H1}...a_{HW}

输出

打印一对符合情况的红细胞和蓝细胞的位置集合,如下:

  • 第一 H 线应描述红细胞的位置。
  • 以下 1 行应为空。
  • 以下 H 线应描述蓝色单元格的位置。

红色或蓝色单元格位置的描述应遵循紫色单元格位置描述的格式。


示例输入 1

5 5
.....
.#.#.
.....
.#.#.
.....

示例输出 1

.....
#####
#....
#####
.....

.###.
.#.#.
.#.#.
.#.#.
.....

红细胞和蓝细胞的位置集合中的一对可能的如下:


示例输入 2

7 13
.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.............

示例输出 2

.............
.###########.
.###.###.###.
.###.###.###.
.###.###.###.
.###.###.###.
.............

.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#########.
.............

红细胞和蓝细胞的位置集合中的一对可能的如下: