[厦门小学生 C++ 2025] 故障机器人

有一个网格，由 $n$ 行和 $m$ 列组成。网格的每个单元格要么是空的，要么是一堵墙。其中有一个空单元内有一个实验室。网格边界外全部是墙。 一个故障机器人从一个实验室逃了出来。它目前在网格的某个空单元中。你可以向机器人发送以下命令之一：“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令意味着移动到相应方向的相邻单元格。 然而，由于机器人故障了，除了听从命令，它什么都会做。收到命令后，它将选择一个与命令方向不同的可通行的方向。如果找不到不听指令的移动方法，那么它什么都不做。 我们想让机器人到达实验室从而可以修理它。对于每个空单元，确定机器人是否可以从该单元开始到达实验室。也就是说，在机器人的每一步之后，都可以向机器人发送一个命令，使得无论机器人选择什么方向，它最终都能进入实验室。 ## Input 本题有多组数据。 第一行包含一个整数 $T$，表示数据组数。 每个测试样例的第一行包含两个整数 $n$ 和 $m$，表示网格中的行数和列数。 接下来有 $n$ 行，每行表示网格的一行，包括 $m$ 个 $C_{i,j}$ 字符。包括以下三种类型之一： - `.` — 单元格是空的； - `#` — 单元格被阻塞； - `L` — 单元格内有一个实验室。 题目保证网格仅包含一个实验室。 ## Output 对于每个测试样例，找到可以使机器人到达实验室的空格。对于原网格图，将可以到达实验室的空格替换为加号 (`+`)，打印新的网格。 [samples] ## Note ### 【样例解释】 在第一个测试样例中，没有可以使机器人到达实验室的空格。考虑一个角空格。给定任何方向，它将移动到相邻的边界空格。现在考虑一个非角空格。无论你向机器人发送什么方向，它都可以选择不同的方向，这样它就会走回角落里。 在最后一个测试样例中，您可以继续向机器人发送与实验室方向相反的命令，机器人将别无选择，只能向实验室移动。 ### 【数据范围】 对于 $20\%$ 的数据：$1 \leq T \leq 10, 1 \leq n, m \leq 10$； 对于另外 $20\%$ 的数据：$n, m$ 至少有一个为 $1$； 对于 $100\%$ 的数据：$1 \leq T \leq 10000, 1 \leq n, m \leq 10^6$，且对于 $T$ 组样例中 $n \times m$ 的总和小于等于 $10^6$。$C_{ij}$ 属于 $\{\tt{., \#, L}\}$，且有且仅有一个 $C_{ij} = \tt L$。