【题解】B4335 [中山市赛 2023] 互质

#include<bits/stdc++.h>
using namespace std;
int n,a[20][20],ans;
pair<int, int> p[120];
int sum[110]={0};
bool v[15][15] = {0};

int dfs(int t,int maxx)//从第t个开始，maxx是相加的和 
{
	if(t==0)//当t=0，即表示所有子矩阵都深搜完  
    {//ans最大的和 
        ans=max(ans,maxx);//返回目前的和与最大的和哪个大，求最大值 
        return 0;
    }
    
    dfs(t-1,maxx);//情况1：不选该子矩阵 
    
    int x=p[t].first; //情况2：选 
    int y=p[t].second;
    for(int i=x;i<=x+2;i++) 
        for(int j=y;j<=y+2;j++) 
            if (v[i][j]==1) //如果已经被选过了直接返回 
				return 0;
   

    for(int i=x;i<=x+2;i++)
        for(int j=y;j<=y+2;j++) 
			v[i][j]=1;//没选过，打上标记 
        
    dfs(t-1,maxx+sum[t]);//加上该矩阵的和，继续搜 

    for(int i=x;i<=x+2;i++) 
        for(int j=y;j<=y+2;j++) 
            v[i][j]=0;//回溯 
            
    return 0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	
	int t=0;//子矩阵的数量 
    for(int i=1;i<=n-2;i++) 
	{
        for(int j=1;j<=n-2;j++) 
		{
			t++;
            p[t]={i,j};//储存每个子矩阵的左上角的坐标 
            for(int x=i;x<=i+2;x++) 
                for(int y=j;y<=j+2;y++) 
                    sum[t]+=a[x][y];//算出每个子矩阵的元素和 
        }
    }
    
    dfs(t,0); 
    cout<<ans; 
	return 0;
}