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

const int N = 20;
int n, m, r, c;
int w[N][N];          // w[i][j] 表示第i行第j列上的值
int f[N][N];          // f[i][j] 表示选择了终点为i且长度为j的矩阵最小分值
int cw[N], rw[N][N];  // cw[i]表示第i列的分值, rw[i][j]表示第i列到第j列的分值

int main() {
    cin >> n >> m >> r >> c;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> w[i][j];
        }
    }

    int res = 0x3f3f3f3f;

    // 枚举所有行选择组合（使用bitset）
    for (int mask = 0; mask < (1 << n); mask++) {
        bitset<N> bs(mask);           // 将整数转换为bitset
        if (bs.count() != r) continue; // 选择的行数必须为r

        vector<int> q;                // 储存选中的行索引
        for (int i = 0; i < n; i++) {
            if (bs[i]) q.push_back(i);
        }

        // 计算每列的行内相邻分值
        for (int i = 0; i < m; i++) {
            cw[i] = 0;
            for (int j = 1; j < r; j++) {
                cw[i] += abs(w[q[j]][i] - w[q[j - 1]][i]);
            }
        }

        // 计算任意两列之间的行间分值
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                rw[i][j] = 0;
                for (int k = 0; k < r; k++) {
                    rw[i][j] += abs(w[q[k]][i] - w[q[k]][j]);
                }
            }
        }

        // DP：f[i][j] 表示以列 i 为终点，选择 j 列的最小分值
        memset(f, 0x3f, sizeof f);
        for (int j = 1; j <= c; j++) {
            for (int i = 0; i < m; i++) {
                if (j == 1) {
                    f[i][j] = cw[i];
                } else {
                    for (int k = 0; k < i; k++) {
                        f[i][j] = min(f[i][j], f[k][j - 1] + rw[k][i] + cw[i]);
                    }
                }
                if (j == c) res = min(res, f[i][c]);
            }
        }
    }

    cout << res << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,m,r,c;
int w[N][N]; //w[i][j] 表示第i行第j列上的值 
int f[N][N]; //f[i][j] 表示选择了终点为i且长度为j的矩阵最小分值 
int cw[N],rw[N][N]; //cw[i]表示第i列的分值,rw[i][j]表示第i列到第j列的分值 
int get_count(int x) //统计x中1的个数 
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(x>>i&1) cnt++;
    }
    return cnt;
}
int main()
{
    cin>>n>>m>>r>>c;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>w[i][j];
        }
    }
    int res=0x3f3f3f3f; //答案初始化 
    for(int u=0;u<1<<n;u++) //枚举每种情况 
    {
        if(get_count(u)==r) //当前一共选择了r行 
        {
            vector<int> q; //储存选择的行
            for(int i=0,j=0;i<n;i++) //记录选择的行 
            {
                if(u>>i&1)
                {
                    q.push_back(i);
                }
            }
            for(int i=0;i<m;i++) //枚举每一列 
            {
                cw[i]=0; //储存第i列的分支
                for(int j=1;j<r;j++) //计算第i列相邻的两行之间的分值 
                {
                    cw[i]+=abs(w[q[j]][i]-w[q[j-1]][i]);
                }
            }
            for(int i=0;i<m;i++) //枚举起点 
            {
                for(int j=i+1;j<m;j++) //枚举终点 
                {
                    rw[i][j]=0; //初始化 
                    for(int k=0;k<r;k++) //枚举每一行 
                    {
                        rw[i][j]+=abs(w[q[k]][i]-w[q[k]][j]);
                    }
                }
            }
            memset(f,0x3f,sizeof f); //初始化 
            for(int j=1;j<=c;j++) //枚举长度 
            {
                for(int i=0;i<m;i++) //枚举终点
                {  
                    if(j==1)
                    {
                        f[i][1]=cw[i]; //自己 
                    }
                    else
                    {
                         for(int k=0;k<i;k++) //枚举倒数第二个点 
                        {
                            f[i][j]=min(f[i][j],f[k][j-1]+rw[k][i]+cw[i]);
                        }
                    }
                   res=min(res,f[i][c]); //更新答案 
                }
               
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

子集枚举 $2^n2^mnm$

• 先枚举行的选择，再枚举列的所有选择，然后计算分数，得到最小的分数。

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int g[N][N],back[N][N]; //back储存的是组合后的矩阵
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main()
{
    int n,m,r,c;
    cin>>n>>m>>r>>c;
    for(int i=0;i<n;i++) //原始矩阵
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    int res=2e9;
    for(int i=0;i<1<<n;i++) //枚举行的所有方案
    {
        vector<int> vr;
        int cnt=0;
        for(int k=0;k<n;k++) //计算选择的列的数目和方案
        {
            if(i>>k&1)
            {
                cnt++;
                vr.push_back(k);
            }
        }
        if(cnt!=r) continue; //不是r行的就继续
        for(int j=0;j<1<<m;j++) //枚举列的所有方案
        {
            vector<int> vc;
            int cnt2=0;
            for(int l=0;l<m;l++) //计算选择的行的数目和方案
            {
                if(j>>l&1)
                {
                    cnt2++;
                    vc.push_back(l);
                }
            }   
            if(cnt2!=c) continue;
         
            for(int a=0;a<r;a++) //将选择的行和列组合起来
            {
                for(int b=0;b<c;b++)
                {
                    back[a][b]=g[vr[a]][vc[b]];
                }
            }
            
            //计算分值
            int ans=0;
            
            for(int a=0;a<r;a++)
            {
                for(int b=0;b<c;b++)
                {
                    for(int d=0;d<4;d++)
                    {
                        int x=a+dx[d],y=b+dy[d];
                        if(x<0||x>=r||y<0||y>=c) continue;
                        
                        ans=ans+abs(back[a][b]-back[x][y]);
                    }
                }
            }
            ans/=2; //有重复计算，所以只保留一份
            res=min(res,ans); //更新答案
        }
    }
    cout<<res; 
    return 0;
}