带记录的dfs

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=8;
int g[N][N];
bool vis[N][N];
int res=0;

bool check(int x,int y){
    for(int i=0;i<x;i++)if(vis[i][y])return false;
    for(int r=x-1,c=y-1;r>=0&&c>=0;r--,c--)
        if(vis[r][c])return false;
    for(int r=x-1,c=y+1;r>=0&&c<8;r--,c++)
        if(vis[r][c])return false;
    return true;
}

void dfs(int u,int sum){
    if(u==8)res=max(res,sum);
    for(int i=0;i<8;i++){
        if(check(u,i)){
            vis[u][i]=true;
            dfs(u+1,sum+g[u][i]);
            vis[u][i]=false;
        }
    }
}


int main(){
    memset(vis,false,sizeof(vis));
    for(int i=0;i<8;i++)for(int j=0;j<8;j++)cin>>g[i][j];
    dfs(0,0);
    cout<<res;
    return 0;
}