题解 | 取数游戏

#include <iostream>
using namespace std;
#include<algorithm>
int n,m;
int a[6][6];
int vit[6][6];
long long tt;
int is(int c,int d){
for(int i=-1;i<=1;i++){
    for (int j=-1;j<=1;j++){
int cn=c+i;
int dn=d+j;
if(i==0&&j==0){
    continue;
}
if(cn>=0&&dn>=0&&cn<n&&dn<m){
if(vit[cn][dn]){
    return 0;
}

}

    }
}


return 1;

}

void  def(int e,long long f){
if(e>=m*n){
    tt=max(tt,f);
    return ;
}
def(e+1,f);
int ex=e/m;
int ey=e%m;
if(is(ex,ey)){
    vit[ex][ey]=1;
def(e+1,f+a[ex][ey]);
vit[ex][ey]=0;



}




}

int main(){

int t;
cin>>t;
while(t--){
    
    cin>>n>>m;
for(int i=0;i<n;i++){

    for(int j=0;j<m;j++){
        cin>>a[i][j];
    }
}
tt=0;
def(0,0);
cout<<tt<<endl;

}





    return 0;
}