CF1613E 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$ .
输出格式
对于每个测试样例，找到可以使机器人到达实验室的空单元。给定网格，将空单元格（用点标记）替换为加号（"+"），代表可以使机器人到达实验室的单元格。打印生成的网格。
说明/提示
在第一个测试样例中，没有可以使机器人到达实验室的自由单元。考虑一个角单元格。给定任何方向，它将移动到相邻的边界网格，而不是一个角落。现在考虑一个非角自由单元。无论你向机器人发送什么方向，它都可以选择不同的方向，这样它就会落在角落里。
在最后一个测试样例中，您可以继续向机器人发送与实验室方向相反的命令，机器人将别无选择，只能向实验室移动。