#P16485. Pm10998Reflections镜面反射

Pm10998Reflections镜面反射

题目背景

工程师林澈正在调试一台用于文物搬运的三维机械臂。机械臂夹持着一件珍贵文物,需要从存放点 (0,0,0)(0,0,0) 运送到目标仓位 (X,Y,Z)(X,Y,Z)。机械臂有两种移动方式:一是沿任一坐标轴方向平移一个单位;二是启动车间里预先安装的若干"空间转置镜",将文物关于某一镜面瞬间对称转移到另一侧。每面镜子精密昂贵,最多只能启动一次。林澈希望计算完成搬运所需的最少操作次数,以便评估能耗。

题目描述

在三维空间中,需要把一件物品从点 (0,0,0)(0,0,0) 运送到点 (X,Y,Z)(X,Y,Z)。有两种操作:

  1. 平移:将物品沿某一坐标轴方向移动 11 个单位。即从点 (a,b,c)(a,b,c) 可以移动到 (a+1,b,c)(a+1,b,c)(a1,b,c)(a-1,b,c)(a,b+1,c)(a,b+1,c)(a,b1,c)(a,b-1,c)(a,b,c+1)(a,b,c+1)(a,b,c1)(a,b,c-1) 中的任意一点。

  2. 反射:选择一面给定的镜面,将物品关于该平面做镜像反射。即物品从原位置消失,出现在平面另一侧,使得新旧位置的连线垂直于该平面,且新旧位置到平面的距离相等。每面镜子在整个过程中最多使用一次。

镜面由三组整数给出:

  • 数组 mirrorX 中每个元素 pp 表示一面垂直于 XX 轴的平面 x=px=p
  • 数组 mirrorY 中每个元素 pp 表示一面垂直于 YY 轴的平面 y=py=p
  • 数组 mirrorZ 中每个元素 pp 表示一面垂直于 ZZ 轴的平面 z=pz=p

关于平面 x=px=p 的反射把点 (a,b,c)(a,b,c) 映到 (2pa,b,c)(2p-a,\,b,\,c),其余两组镜面同理。

求把物品从 (0,0,0)(0,0,0) 运到 (X,Y,Z)(X,Y,Z) 所需的最少操作次数(平移与反射各计一次操作)。

输入格式

第一行包含三个整数 nxn_xnyn_ynzn_z,分别表示三组镜面的数量。

第二行包含 nxn_x 个整数,表示 mirrorX 中的元素(若 nx=0n_x=0 则该行为空行)。

第三行包含 nyn_y 个整数,表示 mirrorY 中的元素(若 ny=0n_y=0 则该行为空行)。

第四行包含 nzn_z 个整数,表示 mirrorZ 中的元素(若 nz=0n_z=0 则该行为空行)。

第五行包含三个整数 XXYYZZ,表示目标位置。

输出格式

输出一个整数,表示所需的最少操作次数。

样例

样例输入 1

0 0 0



901 -15761 10634

样例输出 1

27296

样例解释 1

没有任何镜面,只能平移,答案为 901+15761+10634=27296|901|+|-15761|+|10634|=27296

样例输入 2

1 2 1
-2
1 -7
6
9 10 -9

样例输出 2

26

样例解释 2

不用镜面时需要 9+10+9=289+10+9=28 次。更优方案:XX 轴直接走 99 步;YY 轴先走到 7-7 一侧利用两面镜子 y=1y=1y=7y=-7 各反射一次(净效果相当于平移 2×(1(7))=162\times(1-(-7))=16,走 66 步加 22 次反射共 88 次);ZZ 轴直接走 99 步。合计 9+8+9=269+8+9=26 次。

样例输入 3

1 1 1
1054
2233
-2108
739 750 -25

样例输出 3

1514

样例解释 3

虽然有三面镜子,但使用任何一面都不划算,直接平移 739+750+25=1514739+750+25=1514 次即为最优。

样例输入 4

5 1 3
-2 2 -1 0 3
0
-3 2 0
3 -1 2

样例输出 4

5

样例解释 4

XX 轴:关于 x=2x=2 反射一次,位置从 002222 步后反射到 22(或先反射到 44 再走回 33),XX 轴最优为 22 次(走 11 步加反射 11 次);YY 轴直接走 11 步;ZZ 轴直接走 22 步。合计 2+1+2=52+1+2=5 次。

数据范围与约定

对于所有测试数据:

  • 0nx,ny,nz200 \le n_x, n_y, n_z \le 20
  • 每个镜面坐标与 X,Y,ZX,Y,Z 均为整数,且绝对值不超过 10910^9
  • 同一组内的镜面坐标两两不同;
  • 答案保证在 6464 位有符号整数范围内。

提示

  • 注意每面镜子最多只能使用一次,但可以不使用;
  • 反射的位置与物品当前所在位置无关:关于 x=px=p 的反射总是把 aa 映到 2pa2p-a
  • 三个坐标轴之间互不影响,可以分别考虑。