C++(g++ 7.5.0) 解法, 执行用时: 636ms, 内存消耗: 468K, 提交时间: 2023-05-06 11:46:48

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int mod=1e9+7;

int n,m,k;
int g[5][5];

void rot(int x,int y)
{
    swap(g[x+1][y],g[x][y]);
    swap(g[x][y],g[x][y+1]);
    swap(g[x][y+1],g[x+1][y+1]);
}

int dfs(int u,bool flag)
{
    if(u>=2*k) return 0;
    int res1=0,res2=1e9;
    for(int i=1;i<=3;i++)
    {
            for(int j=1;j<=3;j++)
            {
                int ans=g[i][j]+g[i][j+1]+g[i+1][j+1]+g[i+1][j];
                rot(i,j);
                ans+=dfs(u+1,flag^1);
                res1=max(res1,ans);
                res2=min(res2,ans);
                rot(i,j),rot(i,j),rot(i,j);
            }
    }
    if(flag) return res1;
    else return res2;
}

void solve()
{
    cin >> k;
    for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                    scanf("%d",&g[i][j]);
    
    int res=dfs(0,1);
    printf("%d\n",res);
    
}

int main()
{
    int _;
    cin >> _;
    while(_--) solve();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 487ms, 内存消耗: 508K, 提交时间: 2022-08-24 17:17:33

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i=a;i<=b;i++)
#define sf(n) scanf("%d",&n)

int a[5][5];
int k;

int dfs(int sum,int n){
	if(n==2*k) return sum;
	int Min=1e9,Max=0;
	rep(i,1,3){
		rep(j,1,3){
			int x;
            x=a[i][j],a[i][j]=a[i][j+1];a[i][j+1]=a[i+1][j+1];a[i+1][j+1]=a[i+1][j];a[i+1][j]=x;
			int temp=dfs(sum+a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1],n+1);
			Max=max(Max,temp);Min=min(Min,temp);
			x=a[i+1][j];a[i+1][j]=a[i+1][j+1];a[i+1][j+1]=a[i][j+1];a[i][j+1]=a[i][j],a[i][j]=x;
		}
	}
	if(n%2) return Min;
	else return Max;
}

void solve(){
	int t;
	sf(t);
	while(t--){
		sf(k);
		rep(i,1,4){
			rep(j,1,4){
				sf(a[i][j]);
			}
		}
		cout<<dfs(0,0)<<endl;
	}
}

int main(){
	solve();
	
	return 0;
}