#P16485. Pm10998Reflections镜面反射
Pm10998Reflections镜面反射
题目背景
工程师林澈正在调试一台用于文物搬运的三维机械臂。机械臂夹持着一件珍贵文物,需要从存放点 运送到目标仓位 。机械臂有两种移动方式:一是沿任一坐标轴方向平移一个单位;二是启动车间里预先安装的若干"空间转置镜",将文物关于某一镜面瞬间对称转移到另一侧。每面镜子精密昂贵,最多只能启动一次。林澈希望计算完成搬运所需的最少操作次数,以便评估能耗。
题目描述
在三维空间中,需要把一件物品从点 运送到点 。有两种操作:
-
平移:将物品沿某一坐标轴方向移动 个单位。即从点 可以移动到 、、、、、 中的任意一点。
-
反射:选择一面给定的镜面,将物品关于该平面做镜像反射。即物品从原位置消失,出现在平面另一侧,使得新旧位置的连线垂直于该平面,且新旧位置到平面的距离相等。每面镜子在整个过程中最多使用一次。
镜面由三组整数给出:
- 数组
mirrorX中每个元素 表示一面垂直于 轴的平面 ; - 数组
mirrorY中每个元素 表示一面垂直于 轴的平面 ; - 数组
mirrorZ中每个元素 表示一面垂直于 轴的平面 。
关于平面 的反射把点 映到 ,其余两组镜面同理。
求把物品从 运到 所需的最少操作次数(平移与反射各计一次操作)。
输入格式
第一行包含三个整数 、、,分别表示三组镜面的数量。
第二行包含 个整数,表示 mirrorX 中的元素(若 则该行为空行)。
第三行包含 个整数,表示 mirrorY 中的元素(若 则该行为空行)。
第四行包含 个整数,表示 mirrorZ 中的元素(若 则该行为空行)。
第五行包含三个整数 、、,表示目标位置。
输出格式
输出一个整数,表示所需的最少操作次数。
样例
样例输入 1
0 0 0
901 -15761 10634
样例输出 1
27296
样例解释 1
没有任何镜面,只能平移,答案为 。
样例输入 2
1 2 1
-2
1 -7
6
9 10 -9
样例输出 2
26
样例解释 2
不用镜面时需要 次。更优方案: 轴直接走 步; 轴先走到 一侧利用两面镜子 与 各反射一次(净效果相当于平移 ,走 步加 次反射共 次); 轴直接走 步。合计 次。
样例输入 3
1 1 1
1054
2233
-2108
739 750 -25
样例输出 3
1514
样例解释 3
虽然有三面镜子,但使用任何一面都不划算,直接平移 次即为最优。
样例输入 4
5 1 3
-2 2 -1 0 3
0
-3 2 0
3 -1 2
样例输出 4
5
样例解释 4
轴:关于 反射一次,位置从 到 走 步后反射到 (或先反射到 再走回 ), 轴最优为 次(走 步加反射 次); 轴直接走 步; 轴直接走 步。合计 次。
数据范围与约定
对于所有测试数据:
- ;
- 每个镜面坐标与 均为整数,且绝对值不超过 ;
- 同一组内的镜面坐标两两不同;
- 答案保证在 位有符号整数范围内。
提示
- 注意每面镜子最多只能使用一次,但可以不使用;
- 反射的位置与物品当前所在位置无关:关于 的反射总是把 映到 ;
- 三个坐标轴之间互不影响,可以分别考虑。