著名的全球经济危机正在迅速逼近,于是伯曼、贝兰斯和贝尔塔利三个州结成了联盟,并允许所有成员国的居民自由通行其中任何一个的领土。此外,还决定在各州之间修建一条公路,以保证从任何其他州的任何一点都可以到达任何一个国家的任何一点。
由于道路总是很贵,新成立的联盟各州政府要求你帮助他们评估费用。为此,我们向您提供了一张地图,该地图可以表示为由 n 行和 m 列组成的矩形表。地图上的任何单元格要么属于三个州之一,要么是允许修建道路的区域,要么是不允许修建道路的区域。如果某个单元属于某个州,或者道路建在该单元中,则该单元称为可通行。从任何可通过的单元格中,如果与移动相对应的单元格存在并且可以通过,则您可以向上、向下、向右和向左移动。
你的任务是在最少数量的单元内建造一条道路,这样就可以仅使用可通行的单元从任何州的任何单元到达任何其他州的任何单元。
保证最初可以从任何状态的任何单元格到达任何状态的任何单元格,仅沿着其单元格移动。还保证对于任何状态,至少有一个单元属于它。
输入
输入的第一行包含地图的维度 n 和 m (1 ≤ n, m ≤ 1000) - 分别是行数和列数。
接下来的 n 行每行包含 m 个字符,描述地图的行。 1到3的数字代表对应状态的附件。字符“.”对应的是允许修建道路的单元格,字符“#”表示该单元格内不允许修建。
输出
打印一个整数 - 在内部建造道路以连接所有州的所有单元格所需的最小单元格数量。如果这个目标无法实现,则打印 -1。
示例
输入 #1
4 5 11..2 #..22 #.323 .#333
输出 #1
2
输入 #2
1 5 1#2#3
输出 #2
-1