35pts求条

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, m, r, c, a[N][N], dp[N][N], pos[N], ans = 2e9;
int lc[N], cc[N][N];
bool vis[N];
void dfs(int p)
{
	if (p > r)
	{
		memset(lc, 0, sizeof lc);
		memset(cc, 0, sizeof cc);
        for (int j = 1; j <= m; j++)
        {
            for (int i = 2; i <= r; i++)
            {
                lc[j] += abs(a[pos[i]][j] - a[pos[i - 1]][j]);
            }
        }
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                for (int i = 1; i <= r; i++)
                {
                    cc[j][k] += abs(a[pos[i]][j] - a[pos[i]][k]);
                }
            }
        }
		memset(dp, 0x3f, sizeof dp);
		dp[0][0] = 0;
		for (int j = 1; j <= m; j++)
		{
			for (int k = 0; k <= c; k++)
			{
                dp[j][k] = dp[j - 1][k];
			}
			for (int k = 1; k <= c; k++)
			{
				for (int i = 0; i < j; i++)
				{
					if (dp[i][k - 1] != 0x3f3f3f3f)
                    {
                    	if (i == 0) dp[j][k] = min(dp[j][k], dp[i][k - 1] + lc[j]);
                    	else dp[j][k] = min(dp[j][k], dp[i][k - 1] + lc[j] + cc[j][i]);
                    }
				}
			}
		}
		ans = min(ans, dp[m][c]);
		return ;
	}
	for (int i = pos[p - 1] + 1; i <= n; i++)
	{
		if (vis[i]) continue;
		pos[p] = i;
		vis[i] = 1;
		dfs(p + 1);
		vis[i] = 0;
	}
}

int main()
{
	cin >> n >> m >> r >> c;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
		}
	}
	pos[0] = 0;
	dfs(1);
	cout << ans << '\n';
	return 0;
}