CF590C Three States

著名的全球经济危机正在迅速逼近，因此伯曼、伯兰斯和伯塔利三个州组建了一个联盟，并允许所有成员国的居民自由通过任意一个成员国的领土。此外，决定在各州之间修建道路，以保证可以从任何一个国家的任意地点到达其他国家的任意地点。 由于修路总是昂贵的，新成立联盟的各国政府请你帮忙评估成本。为此，你被发放了一张地图，地图可以表示为一个包含 $n$ 行 $m$ 列的矩形表格。地图上的每个格子要么属于三个州中的某一个州，要么是允许修建道路的区域（用 "." 表示），要么是禁止修建道路的区域（用 "#" 表示）。如果一个格子属于某个州，或者在该格子上修建了道路，则称该格子为“可通行”的。你可以从任意一个可通行格子向上、下、左、右移动一格，如果移动到的格子存在且可通行。 你的任务是在尽量少的格子内修建道路，使得能够通过仅经过可通行格子，从任何一个国家的任意格子到达其他国家的任意格子。 保证初始时，每个国家内部的任意两个格子可以互相到达（仅通过本国格子的移动）。保证每个国家至少有一个格子属于它。

输入的第一行包含地图的尺寸 $n$ 和 $m$（$1 \leq n, m \leq 1000$），分别表示行数和列数。 接下来的 $n$ 行每行包含 $m$ 个字符，描述地图的各行。字符 $1$ 到 $3$ 表示该格子属于相应的国家。字符 "." 表示该格子允许修路，字符 "#" 表示该格子禁止修路。

输出一个整数，表示需要修路的最小格子数，使得所有国家的所有格子互相连通。如果无法实现，输出 $-1$。

由 ChatGPT 5 翻译