子集枚举 $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;
}