题解 | #八皇后#

第二次写 八皇后了 感觉还是有点力不从心 诶

感觉DFS跟回溯就是一个东西

其实还是一个搜索问题

处理点比较慢的地方 一是标记访问数组 和 回溯撤销访问标记 这里可用checkboard[i][j] = value value 可用来表示此处已经标记了皇后的数目 很方便！！用来回溯

还有就是递归终止条件 地方 出现失误 到第八层就够了！！

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
using namespace std;

int checkboard[10][10];
int n;
vector<int> path;
vector<vector<int>> res;

void mark(int x, int y){
    for(int i = 1; i <= 8; i++){
        checkboard[x][i]++;
        checkboard[i][y]++;
    }
    for(int i = x - 1, j = y - 1; i >= 1&& j >= 1; i--,j--){
        checkboard[i][j]++;
    }
    for(int i = x + 1, j = y + 1; i <= 8&& j <= 8; i++,j++){
        checkboard[i][j]++;
    }
    for(int i = x - 1, j = y + 1; i >= 1&& j <= 8; i--,j++){
        checkboard[i][j]++;
    }
    for(int i = x + 1, j = y - 1; i <= 8&& j >= 1; i++,j--){
        checkboard[i][j]++;
    }

}

void undoMark(int x, int y){ //回溯撤销标记
    for(int i = 1; i <= 8; i++){
        checkboard[x][i]--;
        checkboard[i][y]--;
    }
    for(int i = x - 1, j = y - 1; i >= 1&& j >= 1; i--,j--){
        checkboard[i][j]--;
    }
    for(int i = x + 1, j = y + 1; i <= 8&& j <= 8; i++,j++){
        checkboard[i][j]--;
    }
    for(int i = x - 1, j = y + 1; i >= 1&& j <= 8; i--,j++){
        checkboard[i][j]--;
    }
    for(int i = x + 1, j = y - 1; i <= 8&& j >= 1; i++,j--){
        checkboard[i][j]--;
    }

}

bool DFS(int x, int y){ //其实跟回溯板子真的很像 更喜欢这种吧
    if(x == 8) { //边界判断条件
        res.push_back(path);
        return true;
    }
    if(checkboard[x][y] == 1) return false; //如果这个地方有点多余了
    for(int j = 1; j <= 8; j++){
        if(checkboard[x + 1][j] > 0) continue; //若已标记过 则跳过
        mark(x + 1,j); //标记
        path.push_back(j); //放入path中
        DFS(x + 1,j);//继续遍历
        path.pop_back(); //撤销 回退
        undoMark(x + 1,j); //撤销回退
    }

    return false;


}



int main() {
    memset(checkboard, 0, sizeof(checkboard));
    DFS(0,0);
    int b;
    while (cin >>  b) { // 注意 while 处理多个 case
        vector<int> ans = res[b - 1];
        for(auto i : ans) cout << i;
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")