A2788. 解谜
编程题
提高+/省选-
知识点
题目描述
奶牛们一个鲜为人知的事实是它们爱解谜！Bessie生日时农夫约翰给了她一个有趣的机械锁给她解决。锁由三个模块构成，每一个模块都由1x1的小立方体粘连而成。每一个模块都是一个“连通”的模型，那么，你就可以通过在模型上的小正方体间向北、南、东或西走而从模型的一个小正方形到达模型上的任何其他小正方形。
一个模块可以多次向东西南北滑动一个单位。拼图的目标是滑动模块使其分离——即使它们的边界框不再有任何重叠。给定三个模块的形状与位置，请你帮助Bessie找到达到目标需要的最小滑动次数。
一个模块可以多次向东西南北滑动一个单位。拼图的目标是滑动模块使其分离——即使它们的边界框不再有任何重叠。给定三个模块的形状与位置，请你帮助Bessie找到达到目标需要的最小滑动次数。
输入格式
第1行：三个整数N1,N2,N3，表示组成模块1,2,3的小正方体数目。
第2行到第N1+1行：读入一对坐标（x，y），每对坐标表示组成模块1的一个小正方体西南角落的位置。所有坐标在0..9之间。
第N1+2行到第N1+N2+1行：读入一对坐标（x，y），每对坐标表示组成模块2的一个小正方体西南角落的位置。所有坐标在0..9之间。
第N1+N2+2行到第N1+N2+N3+…
第2行到第N1+1行：读入一对坐标（x，y），每对坐标表示组成模块1的一个小正方体西南角落的位置。所有坐标在0..9之间。
第N1+2行到第N1+N2+1行：读入一对坐标（x，y），每对坐标表示组成模块2的一个小正方体西南角落的位置。所有坐标在0..9之间。
第N1+N2+2行到第N1+N2+N3+…
输出格式
* 第 1 行：分离三个对象所需的最小移动次数，如果无法分离对象，则为 -1。
输入输出样例
输入 #1
12 3 5 0 0 1 0 2 0 3 0 3 1 0 1 0 2 0 3 0 4 1 4 2 4 3 4 2 1 2 2 1 2 2 3 3 3 4 3 4 4 4 2
输出 #1
5
说明/提示
模块1由12块小正方体制造，模块2由3块小正方体制造，模块3由5块小正方体制造。最后的图像在如上。（吃图？！）
A：模块1方块 B：模块2方块 C：模块3方块 *：啥都木有
A A A A C
A * C C C
A B B * C
A * B A *
A A A A *
假如我们把模块3向东移一个单位，然后把模块2向北移一个单位，然后把模块1向西移三个单位，就满足了条件。
A：模块1方块 B：模块2方块 C：模块3方块 *：啥都木有
A A A A C
A * C C C
A B B * C
A * B A *
A A A A *
假如我们把模块3向东移一个单位，然后把模块2向北移一个单位，然后把模块1向西移三个单位，就满足了条件。