Description

经过一段时间的运营，有趣张发现了一个很糟糕的情况：由于有趣张那个犇III水平的施工队技术太差，有些道路已经不能通行了！

为了快（妹）递（纸）事业不受影响，有趣张粪发涂墙，决定尽快修好这些道路。

你可以把群岛上的所有地点想象为在一个n*m的表格的格点，而路只能铺在表格的边上。建设一条纵向的路需要的时间为1，而横向的路则需要2的时间。有趣张的工程队必须现在最短的时间内将所有地点连接起来，但犇III水平的工程队却不能并行修建，也就是说同一时间只能修一条道路（什么！还不赶快换i7……）。现在请你计算出有趣张的工程队最短需要多少时间才能把所有地方都连接起来。

如下图，左图为道路当前的情况，右图为抢修后的情况。

Input Format

第一行包含两个数字n和m，1≤n, m≤100。下面有一个n*m的矩阵，第i行j列的数字Ai,j表示了地点(i, j)和地点(i, j+1)及地点(i+1, j)之间的道路情况：

0表示(i, j)和(i, j+1)及(i+1, j)没有任何一条道路是连通的；

1表示(i, j)和(i+1, j)之间有道路连接；

2表示(i, j)和(i, j+1)之间有道路连接；

3表示(i, j)和(i, j+1)及(i+1, j)之间都有道路连接。

Output Format

输出数据只需要包含一个整数，即抢修路需要的最短时间。

Sample Input

4 5
2 1 1 2 1
0 3 0 1 0
3 0 0 3 1
0 2 0 2 0

Sample Output

6

Hint

【题解】

按从小到大顺序加边，跑kruskal

# include <stdio.h>
# define FAST __attribute__((optimize("-O2")))
using namespace std;
int n,m,xy,fu,fv;
int an=0,f[120010];
FAST inline int g(int x,int y) {
	return x*m-m+y;
}
FAST inline int getfather(int x) {
	int r=x;
	while(f[r]!=r) r=f[r];
	int i=x,j;
	while(i!=r) {
		j=f[i];
		f[i]=r;
		i=j;
	}
	return r;
}
int cnt=0,ans=0;
#define kruskal(pos1,pos2,w) { \
	fu=getfather(pos1),fv=getfather(pos2); \
	if (fu!=fv) { \
		f[fu]=fv; \
		ans+=w,cnt++; \
		if(cnt==n*m-1) { \
			printf("%d\n",ans); \
			return 0; \
		} \
	} \
} 
FAST int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=(n+1)*(m+1);++i) f[i]=i;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) {
			scanf("%d",&xy);
			int gn=g(i,j);
			if(!xy) continue;
			if(xy!=2) kruskal(gn,g(i+1,j),0);
			if(xy!=1) kruskal(gn,g(i,j+1),0);		
		}
	for (int i=1;i<n;++i)
		for (int j=1;j<=m;++j) kruskal(g(i,j),g(i+1,j),1);
	for (int i=1;i<=n;++i)
		for (int j=1;j<m;++j) kruskal(g(i,j),g(i,j+1),2);
	return 0;
}