#P17520. [ECUSTPC 2026 Fall] 一般攻击魔法
[ECUSTPC 2026 Fall] 一般攻击魔法
背景
“Zoltraak.”
题目描述
在一个 的二维网格图中,网格中的每个格子可以处于以下三种状态之一:
/(正斜杠镜子):双面反光。光线在此发生 偏折,即连通(上方与左方)以及(下方与右方)。\(反斜杠镜子):双面反光。光线在此发生 偏折,即连通(上方与右方)以及(下方与左方)。.(空格子):无障碍物。光线在此不发生偏折,即连通(上方与下方)以及(左方与右方)。
初始时,网格中的部分格子已经固定放入了 / 或 \ 镜子。其余格子目前为空。对于每一个初始为空的格子,你可以选择将其保留为空,或者将其替换为 / 镜子,或者将其替换为 \ 镜子。
整个网格的外侧由 条单位长度的线段包围。光线只能从这些线段的中点垂直射入或射出。
现给定一束光线的初始射入位置以及目标射出位置,请问是否存在一种合法的网格填充方案,使得光线从指定位置射入网格后,经过若干次直线传播与镜面反射,最终恰好在指定位置射出?
如果存在合法方案,请构造一个填充后的网格,使得光线从指定位置射入并从目标位置射出的过程中,经过的格子数最少。每进入一个格子计数一次;若多次经过同一个格子,则重复计数。若有多种最优方案,输出任意一种即可。否则,请报告无解。
输入格式
第一行输入一个整数 (),表示测试数据的数量。
每组测试数据第一行输入两个整数 和 (),表示网格的行数和列数。
随后 行,每行输入一个长度为 的字符串,表示网格的初始状态。其中 / 表示正斜杠镜子,\ 表示反斜杠镜子,. 表示空格子。
随后一行包含四个用空格隔开的参数 。前两个参数描述初始射入位置,后两个参数描述目标射出位置。其中:
- 为字符,属于 U, D, L, R 之一,分别表示网格的上、下、左、右边界。
- 为正整数,表示光线从该边界的第 个格子的外边缘中点垂直射入或射出。若边界为 U 或 D,则 表示列号();若边界为 L 或 R,则 表示行号()。
保证 。
保证所有测试数据的 。
输出格式
对于每组测试数据,若存在合法方案,输出 行,每行输出一个长度为 的字符串,表示填充后的网格。否则,输出一行 IMPOSSIBLE。
请注意,在绝大多数编程语言中,为了输出 \ ,你需要使用 \\ 来进行转义。
3
2 2
..
..
L 1 U 2
4 4
/\/\
/\/.
....
./..
L 2 L 4
4 4
/\/\
/\/.
..\/
./..
L 2 L 4
./
..
/\/\
/\//
.//.
./..
IMPOSSIBLE
提示
对于第 组测试数据,光线从第 行的左边界射入(向右),经过 遇到 . 继续向右,经过 遇到 / 向上偏折,从第 列的上边界射出(向上)。