CF1613E.Crazy Robot

There is a grid, consisting of $n$ rows and $m$ columns. Each cell of the grid is either free or blocked. One of the free cells contains a lab. All the cells beyond the borders of the grid are also blocked.

A crazy robot has escaped from this lab. It is currently in some free cell of the grid. You can send one of the following commands to the robot: "move right", "move down", "move left" or "move up". Each command means moving to a neighbouring cell in the corresponding direction.

However, as the robot is crazy, it will do anything except following the command. Upon receiving a command, it will choose a direction such that it differs from the one in command and the cell in that direction is not blocked. If there is such a direction, then it will move to a neighbouring cell in that direction. Otherwise, it will do nothing.

We want to get the robot to the lab to get it fixed. For each free cell, determine if the robot can be forced to reach the lab starting in this cell. That is, after each step of the robot a command can be sent to a robot such that no matter what different directions the robot chooses, it will end up in a lab.

有一个由 $n$ 行和 $m$ 列组成的网格。网格中的每个单元格要么是空闲的，要么是被阻塞的。其中一个空闲单元格中设有一间实验室。网格边界之外的所有单元格也均被视为被阻塞。

一台疯狂的机器人已从该实验室逃出，目前正位于网格中的某个空闲单元格内。你可以向机器人发送以下命令之一：“向右移动”、“向下移动”、“向左移动”或“向上移动”。每条命令表示向对应方向的相邻单元格移动。

然而，由于机器人是疯狂的，它会故意不执行你发出的命令。当接收到一条命令后，它将选择一个与命令方向不同、且朝该方向的相邻单元格未被阻塞的方向进行移动。如果存在这样的方向，它就会朝该方向的相邻单元格移动；否则，它将保持不动。

我们的目标是将机器人引导回实验室，以便修复它。对于每个空闲单元格，请判断：若机器人初始位于该单元格，是否存在一种策略（即在机器人每一步之后均可发送一条命令），使得无论机器人每次选择哪个合法的、不同于命令方向的移动方向，它最终都必然到达实验室。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$; $n \cdot m \le 10^6$) — the number of rows and the number of columns in the grid.

The $i$-th of the next $n$ lines provides a description of the $i$-th row of the grid. It consists of $m$ elements of one of three types:

• '.' — the cell is free;
• '#' — the cell is blocked;
• 'L' — the cell contains a lab.

The grid contains exactly one lab. The sum of $n \cdot m$ over all testcases doesn't exceed $10^6$.

第一行包含一个整数 $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$。

For each testcase find the free cells that the robot can be forced to reach the lab from. Given the grid, replace the free cells (marked with a dot) with a plus sign ('+') for the cells that the robot can be forced to reach the lab from. Print the resulting grid.

对于每个测试用例，找出机器人能够被强制到达实验室的空闲格子。给定网格，将能够被强制到达实验室的空闲格子（标记为英文句点 .）替换为加号 '+'。输出处理后的网格。

In the first testcase there is no free cell that the robot can be forced to reach the lab from. Consider a corner cell. Given any direction, it will move to a neighbouring border grid that's not a corner. Now consider a non-corner free cell. No matter what direction you send to the robot, it can choose a different direction such that it ends up in a corner.

In the last testcase, you can keep sending the command that is opposite to the direction to the lab and the robot will have no choice other than move towards the lab.

在第一个测试用例中，不存在任何空闲格子，使得机器人能被强制从该格子抵达实验室。考虑一个角落格子：无论给定哪个方向指令，机器人都会移动到一个相邻的、非角落的边界格子。再考虑一个非角落的空闲格子：无论你向机器人发送哪个方向指令，它总可以选择另一个方向，从而最终停留在某个角落格子。

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