Problem D: PIPI玩三国

Problem D: PIPI玩三国

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 132  Solved: 33
[Submit] [Status] [Web Board] [Creator:]

Description

东汉末年,天下三分,曹操踞北方,刘备踞西川,孙权踞江夏。PIPI想作为第四方大势力,一统天下,成就王霸之业。然而近视眼的他却选错了模式,进入了娱乐模式。
在该模式下,三个国家友好往来,而PIPI需要修建道路使得三个国家能互相到达。
已知三国的地图是一个n*m的区域,每块格子的类型有以下几种:
 '.':表示该格子为空地,可以修路。
'#':表示该格子为障碍,不可被通过,也不可修路。
数字'1'、'2'、'3':表示该格子属于某个国家。
现规定一个格子可以通过的条件是它属于某个国家,或者在它上面修建了道路。对于任何一个可通过的格子,你可以向上/下/左/右四个方向相邻的可通过格子移动。
虽然一统天下的梦是无法实现了,但是PIPI可以成为三国修路之王。请你帮助PIPI计算最少要修建多少道路,才能使得三个国家能互相到达。

Input

第一行两个正整数n和m,其中:2<=n<=1000,2<=m<=1000。
接下来n行,每行m个字符,表示三国的地图。保证同一个国家的格子刚开始可以只通过本国家的领土相互到达,且地图上每个国家至少有一个格子。

Output

输出一个数字,表示PIPI最少要修建多少道路。若没有可行方案,则输出-1。

Sample Input

4 5
11..2
#..22
#.323
.#333

Sample Output

2

HINT

样例解释:
在(1,3),(2,3)处修路(x代表修路的格子),可使得三个国家互相到达。
11x.2
#.x22
#.323
.#333 
可以证明再无更少的修路方法。