SP2052 CERC07H - Hexagonal Parcels

一个刚刚从捷克技术大学毕业的土木工程师遇到了一个有趣的问题，并向我们寻求帮助。这个问题偏向经济方面，而非工程技术。工程师需要在几个建筑物之间建立基础设施。然而，投资者并不拥有这些建筑物之间的所有土地。因此，必须先购买一些土地。 土地被划分成规则的六边形格子，每个地块都是独立的单元，并且都价值相同。其中一些地块已经属于投资者，自成四个连通区域，每个区域包含一个建筑物，需要彼此连接。你的任务是找出使这四个区域连接所需购买的最少地块数。 土地呈现完整的六边形形状，六条边上各有 $H$ 个地块。上图展示了一个 $H = 4$ 的例子，其中字母代表需要连接的四个区域。在这个例子中，需要购买四个额外的地块，其中一个可行方案用叉号标记。

输入包含多个场景。每个场景以一个整数 $H$ 开始，表示土地的大小，$2 \le H \le 20$。接下来有 $2H - 1$ 行，每行表示土地的“行”（如图所示的布局）。每一行包含一个字符，代表每个地块。第 1 行包含 $H$ 个字符，第 2 行包含 $H + 1$ 个字符，依此类推。最长的一行为中间行，包含 $2H - 1$ 个字符，然后每行字符数递减，最后一行再次包含 $H$ 个地块。 用来表示地块的字符可以是一个点（`.`），表示土地不属于投资者，或者用大写字母 `A`、`B`、`C` 或 `D` 表示。相同字母的地块区域总是连通的，也就是说，在同一区域的任意两个地块之间存在一条只通过该区域的路径。 为了提升输入的可读性，各行中可以包含任意数量的空格。两个字母（或点）之间总至少有一个空格。在土地描述结束后，会有一个空行，然后进入下一个场景。最后一个场景后会有一行包含数字零的行。

对于每个场景，输出一行「你需要购买 $P$ 个地块。」其中，$P$ 是所有四个区域实现连通所需购买的最少地块数。 如果能在购买地块之间找到一条路径，将视这些区域为连通。 **本翻译由 AI 自动生成**