【題解】ZeroJudge c104: 00167 – The Sultan’s Successors

#include <iostream>
using namespace std;

int a[8][8];
int has_queen[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
int maxi;
int temp;

bool check(int r, int c){
    for (int i = 0; i < 8; i++){
        if (has_queen[i] >= 0 && (has_queen[i]==c || abs(i-r)==abs(has_queen[i]-c))){
            return false;
        }
    }
    return true;
}

void max_queen(int row){
    if (row == 8){
        maxi = max(maxi, temp);
    }else{
        for (int col = 0; col < 8; col++){
            if (check(row, col)){
                has_queen[row] = col;
                temp += a[row][col];
                max_queen(row+1);
                has_queen[row] = -1;
                temp -= a[row][col];
            }
        }
    }
}

int main(){
    int num;
    cin >> num;
    for (int n = 0; n < num; n++){
        for (int iter = 0; iter < 8; iter++){
            has_queen[iter] = -1;
        }
        for (int i = 0; i < 8; i++){
            for (int j = 0; j < 8; j++){
                cin >> a[i][j];
            }
        }
        maxi = 0;
        temp = 0;
        max_queen(0);
        cout << maxi << endl;
    }
}