← 返回题目列表

Codeforces · 2057/G

G. 秘密消息

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

每周六晚上,平行X的老师Alexander B.都会给平行B的老师Alexander G.写一条秘密信息。由于当时Alexander G.正在演讲,而且信息非常重要,所以Alexander B.必须将这条信息写在在线互动板上。

交互式在线板是一个由 $$$n$$$ 行和 $$$m$$$ 列组成的网格,其中每个单元格的大小为 $$$1 \times 1$$$。该板上的某些单元格已被填满,无法在其中写入消息;这些单元格用符号“.”标记,而其余单元格称为空闲单元格并用符号“#”标记。

先介绍一下网上棋牌的两个特点:

- $$$s$$$ 是可用单元格的数量。
- $$$p$$$ 是由自由单元格并集形成的网格图形的周长。

令 $$$A$$$ 为空闲单元格的集合。您的目标是找到一组满足以下属性的单元格 $$$S \subseteq A$$$:

- $$$|S| \le \frac{1}{5} \cdot (s+p)$$$。
- $$$A$$$ 中的任何单元格要么位于 $$$S$$$ 中,要么与 $$$S$$$ 中的某些单元格共享一侧。

我们可以证明至少存在一组满足这些属性的$$$S$$$;您需要找到任何合适的。

输入

第一行包含数字 $$$t$$$ ($$$1 \le t \le 80\,000$$$) — 测试用例的数量。

在每个测试用例的第一行,数字 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^6$$$) — 给出了网格的尺寸。

以下 $$$n$$$ 行包含网格的描述。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^6$$$。

输出

对于每个测试用例,输出由 $$$m$$$ 符号组成的 $$$n$$$ 行,其中每个符号对单元的状态进行编码:

- "#" — 单元格位于 $$$A$$$ 中,但不在 $$$S$$$ 中;
- “S”— 单元格同时位于 $$$A$$$ 和 $$$S$$$ 中;
- “。” — 该单元既不在 $$$A$$$ 中也不在 $$$S$$$ 中。

示例

输入 #1

3
3 3
.#.
###
.#.
2 6
######
######
3 7
###....
#.#.###
###....

输出 #1

.#.
#S#
.#.
#S##S#
#S##S#
S#S....
#.#.S#S
S#S....

注意

在第一个示例中,$$$s=5$$$ 且 $$$p=12$$$,因此 $$$S$$$ 中的单元格数量不得超过 $$$\frac{1}{5} \cdot (5+12) = 3.4$$$,即 $$$|S| \le 3$$$。请注意,所呈现的集合 $$$S$$$ 由 $$$1$$$ 单元格组成,并且显然满足所有约束。

在第二个示例中,$$$s=12$$$ 和 $$$p=16$$$,因此 $$$S$$$ 中的单元格数量不得超过 $$$\frac{1}{5} \cdot (12+16)= 5.6$$$,即 $$$|S| \le 5$$$。请注意,所呈现的集合 $$$S$$$ 由 $$$4$$$ 单元格组成,并且显然满足所有约束。

在第三个示例中,我们将解释什么是周长,因为它可能并不明显。任何网格图形都有一个边界,它可以表示为在内部点不相交的线段的并集。因此,在下图中,粗黑线表示由自由单元并集形成的图形的边界。这些段的总长度是$$$p=24$$$。

同时,值$$$s=11$$$,上限为$$$|S| \le 7$$$,所呈现的集合的大小为 $$$6$$$ 并且显然满足所有约束。