Problem E: 造桥游戏

Problem E: 造桥游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 409  Solved: 43
[Submit] [Status] [Web Board] [Creator:]

Description

在一片海域中,分散着许多陆地,而PIPI想给陆地之间造桥,使得所有陆地能互相到达。
海域是一片n*m的区域,每块格子的类型有以下几种:
'0':表示此处是海水。
'1':表示此处是陆地。
现规定,设陆地1的坐标为(x1,y1),陆地2的坐标为(x2,y2),那么在陆地1和陆地2之间建桥的代价,是从(x1,y1)进行上/下/左/右四个方向的移动,到达(x2,y2)时路上所经过的海水格子的数量。
请问PIPI使得所有陆地能互相到达的最小造桥代价是多少?

Input

第一行两个正整数n和m,其中n,m<=1000。
接下来一个n*m的矩阵,表示这片海域的情况,保证‘1’的个数>1。

Output

输出PIPI使所有陆地能互相到达的最小造桥代价。

Sample Input

3 4
1001
0010
0000

Sample Output

3

HINT

样例解释:
在(0,0)与(0,3)两块陆地间造桥的最小代价是2。
在(0,3)与(1,2)两块陆地间造桥的最小代价是1。
因此总的最小造桥代价即为3。


切勿以为是这样造桥,从而总的最小造桥代价为2。
1111
0010
0000