#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;
}