这题很明显是一个最小生成树，节点是每个格子，然后从每个格子向四个方向连边。

1.节点编号

不知道有没有用一维数组当二维数组用过。我们设 a[i][j] 表示第 \(i\) 行，第 \(j\) 列，每行 \(n\) 个元素，那么转化为一维数组就是 a[(i-1)*n+j]。这个应该很好想通，有 \(i\) 行说明前面已经有了 \((i-1)\times n\) 个元素，再加上这行的 \(j\) 个元素就得了。由于下标是从 \(0\) 开始的，我们转成一维的时候就不用减 \(1\) 了。

节点编号同理，\({i,j}\) 转化成 \({i\times n+j}\)。

2.连边

这个好理解，每个节点向四面都连一个边，边权就是两节点高度差的绝对值。

总体代码如下：

cin>>n;
for(int i=0;i<n;++i)
	for(int j=0;j<n;++j)
		cin>>a[i][j];
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
for(int i=0;i<n;++i)
	for(int j=0;j<n;++j)
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(0<=x&&x<n&&0<=y&&y<n)
				edges.push_back(edge(i*n+j,x*n+y,abs(a[i][j]-a[x][y])));
			}

接着，就是 kruskal 了。

注意！

如果你直接使用连通块的个数小于一半是错的。

拿样例来说

5 
0 0 0 3 3 
0 0 0 0 3 
0 9 9 3 3 
9 9 9 3 3 
9 9 9 9 3 

我们所有的 \(0,9,3\) 全部连起来了，此时连通块只有三个，程序肯定会输出 \(0\)，但这种情况明显是错的。

在这里WA的死去活来

于是我们用 size[i] 来表示 \(i\) 所在连通块的大小，当我们合并时也将 size[i] 合并，然后看合并完后的连通块是否满足大于总数的一半。

AC代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
const int maxn=500+5;
struct edge{
	int u,v,dis;
	bool operator<(const edge& rhs)const{
		return dis<rhs.dis;
	}
	edge(int u=0,int v=0,int d=0):u(u),v(v),dis(d){}
};
vector <edge> edges;
int a[maxn][maxn];
int cnt=0;
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
int size[maxn*maxn];
int pa[maxn*maxn];
int root(int x){
	return pa[x]==x?x:pa[x]=root(pa[x]);
}
int main(){
	cin>>n;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			cin>>a[i][j];
	for(int i=0;i<=n*n;++i)
		pa[i]=i,size[i]=1;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			for(int k=0;k<4;k++){
				int x=i+dx[k],y=j+dy[k];
				if(0<=x&&x<n&&0<=y&&y<n)
					edges.push_back(edge(i*n+j,x*n+y,abs(a[i][j]-a[x][y])));
			}
	sort(edges.begin(),edges.end());
	for(int i=0;i<edges.size();++i){
		int x=root(edges[i].u),y=root(edges[i].v);
		if(x!=y){
			pa[x]=y;
			size[y]+=size[x];//由于是直接找到根节点的，只在这里维护连通块大小就好了
			if(size[y]>=(n*n+1)/2){
				cout<<edges[i].dis;
				return 0;
			}
		}
	}
	return 0;
}