计蒜客 八皇后问题（dfs搜索）

计蒜客 八皇后问题

#include <bits/stdc++.h>

using namespace std;
using namespace std;

#define maxn 8
int board[maxn][maxn];
int maxSum = 0;

//值:第0 1 2 3 4....(数组下标)列的皇后在第几行
int queenAtRows[maxn] = {-1};

//第0 1 2 3 4....行是否有皇后
bool rowStatus[maxn] = {false};

//第0 1 2 3 4....正斜线是否有皇后
bool passiveStatus[2 * maxn] = {false};

//第0 1 2 3 4....反斜线是否有皇后
bool negativeStatus[2 * maxn] = {false};

/*
@idx:现在在放第idx个皇后
*/
void dfs(int idx) {
    //递归基
    if(idx >= maxn) {
        int sum = 0;
        for(int col = 0; col < maxn; ++col) { //第col列皇后
            for(int row = 0; row < maxn; ++row) {
                if(queenAtRows[col] == row)
                    sum += board[row][col];
            }
        }

        maxSum = max(maxSum, sum);
        return;
    }

    for(int queenAtRow = 0; queenAtRow < maxn; ++queenAtRow) { //一行一行的尝试放置皇后
        if(!rowStatus[queenAtRow] && !passiveStatus[idx + queenAtRow] && !negativeStatus[idx - queenAtRow + maxn - 1]) {
            rowStatus[queenAtRow] = true;
            passiveStatus[idx + queenAtRow] = true;
            negativeStatus[idx - queenAtRow + maxn - 1] = true;

            queenAtRows[idx] = queenAtRow;
            dfs(idx + 1);//递归尝试放下1个皇后

            //复原现场,回溯法需要重点注意的地方
            rowStatus[queenAtRow] = false;
            passiveStatus[idx + queenAtRow] = false;
            negativeStatus[idx - queenAtRow + maxn - 1] = false;
        }
    }
}


int main() {
    //freopen("data.in", "r", stdin);

    for(int i =0; i < maxn; i++) {
        for(int j = 0; j < maxn; j++) {
            cin >> board[i][j];
        }
    }

    dfs(0);
    cout << maxSum << endl;

    return 0;
}