#2076. Unlocking Blocks

Unlocking Blocks

题目描述

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

一个模块可以多次向东西南北滑动一个单位。拼图的目标是滑动模块使其分离,即使它们的边界框不再有任何重叠。给定三个模块的形状与位置,请你帮助Bessie\red{Bessie}找到达到目标需要的最小滑动次数 。

输入格式

1\red{1 }行:三个空格分隔的整数:N1\red{N1}N2\red{N2 }N3\red{N3,}分别描述组成对象 1\red{1}2\red{2 }3\red{3 }的单位正方形的数量。

2..1+N1\red{2..1+N1 }行:每一行都描述了作为对象 1\red{1 }一部分的单个正方形西南角的 (x,y)\red{(x,y) }位置。所有坐标都在 0..9\red{0..9 }范围内。

2+N1..1+N1+N2\red{2+N1..1+N1+N2 }行:这些行中的每一行都描述了作为对象 2\red{2 }一部分的单个正方形西南角的 (x,y)\red{(x,y) }位置。所有坐标都在范围 0..9.\red{0.. 9.}

2+N1+N2..1+N1+N2+N3\red{2+N1+N2..1+N1+N2+N3 }行:这些行中的每一行都描述了作为对象 3\red{3 }一部分的单个正方形的西南角的 (x,y)\red{(x,y) }位置。所有坐标都位于范围 0..9\red{0..9}

1\red{1}行:三个整数N1,N2,N3\red{N1,N2,N3,}表示组成模块1,2,3\red{1,2,3}的小正方体数目。

2\red{2}行到第N1+1\red{N1+1}行:读入一对坐标(x\red{x,}y\red{y)},每对坐标表示组成模块1\red{1}的一个小正方体西南角落的位置。所有坐标在0..9\red{0..9}之间。

N1+2\red{N1+2}行到第N1+N2+1\red{N1+N2+1}行:读入一对坐标(x\red{x,}y\red{y)},每对坐标表示组成模块2\red{2}的一个小正方体西南角落的位置。所有坐标在0..9\red{0..9}之间。

N1+N2+2\red{N1+N2+2}行到第N1+N2+N3+\red{N1+N2+N3+}img

输出格式

1\red{1 }行:分离三个对象所需的最小移动次数,如果无法分离对象,则为 1\red{-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

输出样例

5

提示

对象 1\red{1 }12\red{12 }个正方形组成,对象 2\red{2 }3\red{3 }个正方形组成,对象 3\red{3 }5\red{5 }个正方形组成。物体的形状如上图所示。

如果我们将对象 3\red{3 }向东滑动一个位置,然后将对象 2\red{2 }向北滑动一个位置,然后将对象 1\red{1 }向西滑动三个位置,那么这三个对象的边界框将不再共享任何重叠。

模块1\red{1}12\red{12}块小正方体制造,模块2\red{2}3\red{3}块小正方体制造,模块3\red{3}5\red{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\red{3}向东移一个单位,然后把模块2\red{2}向北移一个单位,然后把模块1\red{1}向西移三个单位,就满足了条件。