Crazy Robot

题意翻译

#### 题目描述 有一个网格，由 $n$ 行和 $m$ 列组成。网格的每个单元格要么是空的，要么是被阻塞的。其中有一个空单元内有一个实验室。超出网格边界的所有单元格也被阻塞。 一个疯狂的机器人从一个实验室逃了出来。它目前在网格的一些空单元中。您可以向机器人发送以下命令之一：“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令意味着移动到相应方向的相邻单元格。 然而，由于机器人很疯狂，除了听从命令，它什么都会做。收到命令后，它将选择一个方向，使其与命令中的方向不同，并且该方向上的单元没有被阻塞。如果有这样的方向上的单元没有被堵塞，那么它就会移动到那个方向上的相邻单元格。否则，它什么都不做。 我们想让机器人到达实验室从而可以修理它。对于每个空单元，确定机器人是否可以从该单元开始到达实验室。也就是说，在机器人的每一步之后，都可以向机器人发送一个命令，这样无论机器人选择什么不同的方向，它最终都会进入实验室。 #### 输入格式 第一行包含一个整数 $t$ $( 1 \le t \le 1000 )$ ，表示数据组数。 每个测试样例的第一行包含两个整数‎‎ $n$‎ 和 $‎‎m$‎ $( ‎1 \le n,m \le 10^6‎‎)$，表示网格中的行数和列数。‎ 接下来有‎‎ $n$‎ 行，每行表示网格的一行，包括‎‎‎ $‎‎m$‎ 个字符。包括以下三种类型之一：‎ - ‎'.' — 单元格是空的； - ‎'#' — 单元格被阻塞； - ‎'L' — 单元格内有一个实验室。 ‎网格仅包含一个实验室。总和‎‎ $n \cdot m$ ‎‎在所有测试样例中不超过 $10^6$ ‎.‎ #### 输出格式 ‎对于每个测试样例，找到可以使机器人到达实验室的空单元。给定网格，将空单元格（用点标记）替换为加号（"+"），代表可以使机器人到达实验室的单元格。打印生成的网格。‎ #### 说明/提示 ‎在第一个测试样例中，没有可以使机器人到达实验室的自由单元。考虑一个角单元格。给定任何方向，它将移动到相邻的边界网格，而不是一个角落。现在考虑一个非角自由单元。无论你向机器人发送什么方向，它都可以选择不同的方向，这样它就会落在角落里。‎ ‎在最后一个测试样例中，您可以继续向机器人发送与实验室方向相反的命令，机器人将别无选择，只能向实验室移动。‎

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

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

说明

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.