P3053 [USACO12OPEN] Unlocking Blocks S
题目描述
一个鲜为人知的事实是，奶牛非常喜欢解谜！为了庆祝贝西的生日，农夫约翰给了她一个有趣的机械谜题让她来解决。这个谜题由三个实心物体组成，每个物体都是由 1x1 的单位正方形粘合在一起构成的。每个物体都是一个「连通」的形状，也就是说，你可以通过在物体上的正方形向北、南、东或西移动，从物体上的一个正方形到达另一个正方形。
一个物体可以通过不断地向北、南、东或西滑动一个单位来移动。谜题的目标是移动这些物体，使它们分开——即它们的边界框不再有任何正重叠。给定三个物体的形状和位置，你的任务是帮助贝西决定分开这些物体所需的最少滑动次数。
输入格式
\* 第 1 行：三个用空格分隔的整数 $N_1$，$N_2$ 和 $N_3$，分别表示组成物体 1、2 和 3 的单位正方形的数量。
\* 第 2 行到第 $1+N_1$ 行：每行描述一个 (x,y) 坐标，表示组成物体 1 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。
\* 第 $2+N_1$ 行到第 $1+N_1+N_2$ 行：每行描述一个 (x,y) 坐标，表示组成物体 2 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。
\* 第 $2+N_1+N_2$ 行到第 $1+N_1+N_2+N_3$ 行：每行描述一个 (x,y) 坐标，表示组成物体 3 的一个单位正方形的西南角的位置。所有坐标都在 0 到 9 的范围内。
输出格式
\* 第 1 行：分开三个物体所需的最少移动次数，或者如果物体无法分开则输出 -1。
说明/提示
物体 1 由 12 个正方形组成，物体 2 由 3 个正方形组成，物体 3 由 5 个正方形组成。物体的形状如上图所示。
如果我们将物体 3 向东滑动一个位置，然后将物体 2 向北滑动一个位置，然后将物体 1 向西滑动三个位置，那么三个物体的边界框将不再有任何重叠。
物体 1 由 12 块小正方体制成，物体 2 由 3 块小正方体制成，物体 3 由 5 块小正方体制成。最后的图像如上所示。（吃图？！）
```cpp
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 向西移三个单位，就满足了条件。
感谢 @姚起龙 提供翻译
（由 ChatGPT 4o 翻译）