33OJ
登录 注册

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

    ID: 20248 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>Special Judge广度优先搜索 BFS深度优先搜索 DFS图论建模最短路2026高校校赛

[ECUSTPC 2026 Fall] 一般攻击魔法

背景

“Zoltraak.”

题目描述

在一个 n×mn \times m 的二维网格图中,网格中的每个格子可以处于以下三种状态之一:

  1. /(正斜杠镜子):双面反光。光线在此发生 90∘90^\circ 偏折,即连通(上方与左方)以及(下方与右方)。
  2. \(反斜杠镜子):双面反光。光线在此发生 90∘90^\circ 偏折,即连通(上方与右方)以及(下方与左方)。
  3. .(空格子):无障碍物。光线在此不发生偏折,即连通(上方与下方)以及(左方与右方)。

初始时,网格中的部分格子已经固定放入了 / 或 \ 镜子。其余格子目前为空。对于每一个初始为空的格子,你可以选择将其保留为空,或者将其替换为 / 镜子,或者将其替换为 \ 镜子。

整个网格的外侧由 2(n+m)2(n+m) 条单位长度的线段包围。光线只能从这些线段的中点垂直射入或射出。

现给定一束光线的初始射入位置以及目标射出位置,请问是否存在一种合法的网格填充方案,使得光线从指定位置射入网格后,经过若干次直线传播与镜面反射,最终恰好在指定位置射出?

如果存在合法方案,请构造一个填充后的网格,使得光线从指定位置射入并从目标位置射出的过程中,经过的格子数最少。每进入一个格子计数一次;若多次经过同一个格子,则重复计数。若有多种最优方案,输出任意一种即可。否则,请报告无解。

输入格式

第一行输入一个整数 TT (1≤T≤1001 \le T \le 100),表示测试数据的数量。

每组测试数据第一行输入两个整数 nn 和 mm (1≤n×m≤2×1051 \le n \times m \le 2 \times 10^5),表示网格的行数和列数。

随后 nn 行,每行输入一个长度为 mm 的字符串,表示网格的初始状态。其中 / 表示正斜杠镜子,\ 表示反斜杠镜子,. 表示空格子。

随后一行包含四个用空格隔开的参数 d1,p1,d2,p2d_1, p_1, d_2, p_2。前两个参数描述初始射入位置,后两个参数描述目标射出位置。其中:

  • d1,d2d_1,d_2 为字符,属于 U, D, L, R 之一,分别表示网格的上、下、左、右边界。
  • p1,p2p_1,p_2 为正整数,表示光线从该边界的第 pp 个格子的外边缘中点垂直射入或射出。若边界为 U 或 D,则 pp 表示列号(1≤p≤m1 \le p \le m);若边界为 L 或 R,则 pp 表示行号(1≤p≤n1 \le p \le n)。

保证 (d1,p1)≠(d2,p2)(d_1,p_1) \ne (d_2,p_2)。

保证所有测试数据的 ∑(n×m)≤2×105\sum (n \times m) \le 2 \times 10^5 。

输出格式

对于每组测试数据,若存在合法方案,输出 nn 行,每行输出一个长度为 mm 的字符串,表示填充后的网格。否则,输出一行 IMPOSSIBLE。

请注意,在绝大多数编程语言中,为了输出 \ ,你需要使用 \\ 来进行转义。

3
2 2
..
..
L 1 U 2
4 4
/\/\
/\/.
....
./..
L 2 L 4
4 4
/\/\
/\/.
..\/
./..
L 2 L 4
./
..
/\/\
/\//
.//.
./..
IMPOSSIBLE

提示

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