#1050. 「USACO 2012 Open Silver」Unlocking Blocks

一个鲜为人知的事实是，奶牛非常喜欢解谜！为了庆祝贝西的生日，农夫约翰给了她一个有趣的机械谜题让她来解决。这个谜题由三个实心物体组成，每个物体都是由 1x1 的单位正方形粘合在一起构成的。每个物体都是一个「连通」的形状，也就是说，你可以通过在物体上的正方形向北、南、东或西移动，从物体上的一个正方形到达另一个正方形。

一个物体可以通过不断地向北、南、东或西滑动一个单位来移动。谜题的目标是移动这些物体，使它们分开——即它们的边界框不再有任何正重叠。给定三个物体的形状和位置，你的任务是帮助贝西决定分开这些物体所需的最少滑动次数。

* 第 1 行：三个用空格分隔的整数 ， 和 ，分别表示组成物体 1、2 和 3 的单位正方形的数量。

* 第 2 行到第 行：每行描述一个 (x,y) 坐标，表示组成物体 1 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。

* 第 行到第 行：每行描述一个 (x,y) 坐标，表示组成物体 2 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。

* 第 行到第 行：每行描述一个 (x,y) 坐标，表示组成物体 3 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。

* 第 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 个正方形组成。物体的形状如上图所示。

如果我们将物体 3 向东滑动一个位置，然后将物体 2 向北滑动一个位置，然后将物体 1 向西滑动三个位置，那么三个物体的边界框将不再有任何重叠。

物体 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 向西移三个单位，就满足了条件。