← 返回题目
题库练习 解谜
← 上一题 下一题 →

A2788 | 解谜

来源USACO / 2012
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

奶牛们一个鲜为人知的事实是它们爱解谜！Bessie生日时农夫约翰给了她一个有趣的机械锁给她解决。锁由三个模块构成，每一个模块都由1x1的小立方体粘连而成。每一个模块都是一个“连通”的模型，那么，你就可以通过在模型上的小正方体间向北、南、东或西走而从模型的一个小正方形到达模型上的任何其他小正方形。


一个模块可以多次向东西南北滑动一个单位。拼图的目标是滑动模块使其分离——即使它们的边界框不再有任何重叠。给定三个模块的形状与位置，请你帮助Bessie找到达到目标需要的最小滑动次数。
![](/uploads/acgo/image/e748bd18a7c2487b_7888c19eaf9a.png)

输入格式

第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+…

输出格式

* 第 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
C++ 编辑器
输入
输出