取数游戏 题解

朴素dfs

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[7][7];
int b[7][7];
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};
int ans=0;
int sum=0;
void dfs(int x,int y){
    if(x>n){
        ans=max(ans,sum);
        return;
    }
    if(y>m){
        dfs(x+1,1);
        return;
    }
    dfs(x,y+1);
    if(!b[x][y]){
        b[x][y]++;
        for(int i=0;i<8;i++){
            int xx=x+dx[i],yy=dy[i]+y;
            b[xx][yy]++;
        }
        sum+=a[x][y];
        dfs(x,y+1);
        b[x][y]=0;
        sum-=a[x][y];
        for(int i=0;i<8;i++){
            int xx=x+dx[i],yy=dy[i]+y;
            b[xx][yy]--;
        }
    }
}
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        ans=0;
        sum=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>a[i][j];
        }
        dfs(1,1);
        cout<<ans<<"\n";
    }    
    return 0;
}