样例2输出了15，状压+dp：

#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define N 20
using namespace std;
int n,m,r,c,a[N][N],dp[N][N][N],f[N][N],ans=1e9;
vector<int> v;
int check(int x){
	int s=0;
	while(x){
		s++;
		x-=lowbit(x);
	}
	return s==c;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&c);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	for(int i=0;i<(1<<m);i++){
		if(check(i)){
			memset(dp,63,sizeof(dp));memset(f,63,sizeof(f));
			dp[0][0][0]=0;f[0][0]=0;
			for(int j=1;j<=n;j++){
				for(int k=1;k<=j&&k<=r;k++){
					for(int l=k-1;(k>1?l<j:!l);l++){
						int s=0;
						int last=0;
						for(int p=1;p<=m;p++){
							if(i&(1<<p-1)) s+=(last?abs(a[j][p]-a[j][last]):0)+(l?abs(a[j][p]-a[l][p]):0),last=p; 
						}
						dp[j][k][l]=min(f[j-1][k],f[l][k-1]+s);
						f[j][k]=min(f[j][k],dp[j][k][l]);
						if(k==r) ans=min(ans,dp[j][k][l]);
					}
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}