P17520 [ECUSTPC 2026 Fall] 一般攻击魔法

> *“Zoltraak.”*

在一个 $n \times m$ 的二维网格图中，网格中的每个格子可以处于以下三种状态之一： 1. `/`（正斜杠镜子）：双面反光。光线在此发生 $90^\circ$ 偏折，即连通（上方与左方）以及（下方与右方）。 2. `\`（反斜杠镜子）：双面反光。光线在此发生 $90^\circ$ 偏折，即连通（上方与右方）以及（下方与左方）。 3. `.`（空格子）：无障碍物。光线在此不发生偏折，即连通（上方与下方）以及（左方与右方）。 初始时，网格中的部分格子已经固定放入了 `/` 或 `\` 镜子。其余格子目前为空。对于每一个初始为空的格子，你可以选择**将其保留为空**，或者将其**替换为 `/` 镜子**，或者将其**替换为 `\` 镜子**。 整个网格的外侧由 $2(n+m)$ 条单位长度的线段包围。光线只能从这些线段的中点垂直射入或射出。 现给定一束光线的初始射入位置以及目标射出位置，请问是否存在一种合法的网格填充方案，使得光线从指定位置射入网格后，经过若干次直线传播与镜面反射，最终恰好在指定位置射出？ 如果存在合法方案，请构造一个填充后的网格，使得光线从指定位置射入并从目标位置射出的过程中，经过的格子数最少。每进入一个格子计数一次；若多次经过同一个格子，则重复计数。若有多种最优方案，输出任意一种即可。否则，请报告无解。

第一行输入一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的数量。 每组测试数据第一行输入两个整数 $n$ 和 $m$ ($1 \le n \times m \le 2 \times 10^5$)，表示网格的行数和列数。 随后 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示网格的初始状态。其中 `/` 表示正斜杠镜子，`\` 表示反斜杠镜子，`.` 表示空格子。 随后一行包含四个用空格隔开的参数 $d_1, p_1, d_2, p_2$。前两个参数描述初始射入位置，后两个参数描述目标射出位置。其中： - $d_1,d_2$ 为字符，属于 U, D, L, R 之一，分别表示网格的上、下、左、右边界。 - $p_1,p_2$ 为正整数，表示光线从该边界的第 $p$ 个格子的外边缘中点垂直射入或射出。若边界为 U 或 D，则 $p$ 表示列号（$1 \le p \le m$）；若边界为 L 或 R，则 $p$ 表示行号（$1 \le p \le n$）。 保证 $(d_1,p_1) \ne (d_2,p_2)$。 保证所有测试数据的 $\sum (n \times m) \le 2 \times 10^5$ 。

对于每组测试数据，若存在合法方案，输出 $n$ 行，每行输出一个长度为 $m$ 的字符串，表示填充后的网格。否则，输出一行 `IMPOSSIBLE`。 请注意，在绝大多数编程语言中，为了输出 `\` ，你需要使用 `\\` 来进行转义。

对于第 $1$ 组测试数据，光线从第 $1$ 行的左边界射入（向右），经过 $(1, 1)$ 遇到 `.` 继续向右，经过 $(1, 2)$ 遇到 `/` 向上偏折，从第 $2$ 列的上边界射出（向上）。