← 返回题目列表

Codeforces · 1613/E

E. 疯狂机器人

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

有一个网格,由 $$$n$$$ 行和 $$$m$$$ 列组成。网格的每个单元格要么空闲,要么被阻塞。其中一个空闲牢房包含一个实验室。网格边界之外的所有单元格也被阻挡。

一个疯狂的机器人逃离了这个实验室。它当前位于网格的某个空闲单元中。您可以向机器人发送以下命令之一:“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令都意味着移动到相应方向的相邻小区。

然而,由于机器人很疯狂,除了听从命令之外,它会做任何事情。接收到命令后,它将选择一个与命令中的方向不同的方向,并且该方向上的小区不会被阻塞。如果有这样的方向,那么它就会移动到该方向的相邻小区。否则,它什么也做不了。

我们希望将机器人送到实验室进行修复。对于每个空闲单元,确定是否可以强制机器人从该单元开始到达实验室。也就是说,在机器人的每一步之后,都可以向机器人发送命令,这样无论机器人选择什么不同的方向,它最终都会进入实验室。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$; $$$n \cdot m \le 10^6$$$) - 网格中的行数和列数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行提供了网格第 $$$i$$$ 行的描述。它由以下三种类型之一的 $$$m$$$ 元素组成:

- '.' — 细胞是免费的;
- '#' — 单元格被阻止;
- 'L' — 该单元包含一个实验室。

网格仅包含一个实验室。所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,找到机器人可以被迫到达实验室的空闲单元。给定网格,将空闲单元(用点标记)替换为加号(“+”),作为机器人可以被迫到达实验室的单元。打印生成的网格。

示例

输入 #1

4
3 3
...
.L.
...
4 5
#....
..##L
...#.
.....
1 1
L
1 9
....L..#.

输出 #1

...
.L.
...
#++++
..##L
...#+
...++
L
++++L++#.

注意

在第一个测试用例中,没有可以强制机器人到达实验室的空闲单元。考虑一个角单元。给定任何方向,它都会移动到不是角点的相邻边界网格。现在考虑一个非角自由单元。无论您向机器人发送哪个方向,它都可以选择不同的方向,使其最终到达角落。

在最后一个测试用例中,你可以继续发送与实验室方向相反的命令,机器人将别无选择,只能向实验室移动。