seuOJ517 - Nanami and the Golden Sunlight Sunflower Fields

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2024

题目描述

Nanami 和你选择了一块有着金色的阳光向日葵花田的地方养老。

Nanami 有一个 $n\times n$ 的金色阳光向日葵花田，花田中两个格子连通当且仅当两个格子有一条公共边，现在某些格子中已经被种上了向日葵，现在请你再最多再帮她种 $\lfloor \frac{n\times n}{2} \rfloor$ 朵向日葵，使得所有有向日葵的格子构成一个联通块（即任意一对种上向日葵的格子都可以通过向日葵格子互相到达）。

其中 $\lfloor x \rfloor$ 代表对 $x$ 向下取整，例如 $\lfloor \frac{1}{2} \rfloor=0$ 、 $\lfloor \frac{9}{2} \rfloor=4$ 和 $\lfloor \frac{16}{2} \rfloor=8$ 。

输入格式

第一行，一个整数 $t(1\le t \le 50)$，代表数据组数。

对于每组数据：

第一行，一个整数 $n(1\le n \le 50)$，代表花田的大小。

接下来 $n$ 行长度为 $n$ 的仅由 '#' 和 '.' 组成的字符串，'# 代表种植了向日葵的格子，'.' 代表空格子。

输出格式

对于每组数据，输出一个 $n$ 行长度为 $n$ 仅由 '#' 和 '.' 组成的字符串，'# 代表种植了向日葵的格子，'.' 代表空格子，代表你的种植方案，你不能移动原有的向日葵的位置。

可以被证明的是，在题目要求的条件下，一定存在一个种植方案，能够满足 Nanami 的需求，任意满足题目要求的方案都是正确的。

样例

输入样例

6
1
.
2
#.
.#
3
#.#
.#.
#.#
4
..#.
....
##.#
..#.
5
#...#
.....
#...#
.....
#...#
6
.....#
......
......
......
..##..
#.....

输出样例

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