题解 P1219 【八皇后】

#蒟蒻的题解 思路:以行为单位搜索，依次枚举行的每个列，判断在该列放置一个棋子会不会与之前的棋子冲突，如果冲突则考虑下列，如果不冲突则在结果数组中记录当前列并搜索下一行，搜索完下一行后回溯，撤销该列的棋子，继续搜索下一列 ```cpp #include <cstdio> #include <iostream> #include <vector> #include <array> #include <algorithm> #include <functional> #include <cstdlib> using namespace std; using int_t = signed long long int; int_t n; //结果数组 int_t result[15] = {0}; //标明某一列是否被占用 bool colume[15] = {0}; //line-col 标明一条对角线是否被占用 注：由于列减行可能为负，所以本数组访问时下标应该加n bool lu_rd_line[35] = {0}; //line+col 标明另一条对角线是否被占用 bool ld_ru_line[35] = {0}; //在某个位置放置棋子，并在上面三个数组中标记被占用的列和对角线 void place(int_t line, int_t col) { colume[col] = true; lu_rd_line[line - col + n] = true; ld_ru_line[line + col + n] = true; } //在某个位置取消放置棋子，并在三个数组中取消标记被占用的列和对角线 void unplace(int_t line, int_t col) { colume[col] = false; lu_rd_line[line - col + n] = false; ld_ru_line[line + col + n] = false; } //判断某个位置是否可以放棋子 bool canPlace(int_t line, int_t col) { return colume[col] == false && lu_rd_line[line - col + n] == false && ld_ru_line[line + col + n] == false; } //打印结果 void printResult() { for (int i = 1; i <= n; i++) { cout << result[i] << " "; } cout << endl; } //由于题目要求只输出三组解，所以此处需要统计已经得出的结果数目 int_t resultNum = 0; //搜索函数 bool search(int_t line) { //枚举每一列 for (int i = 1; i <= n; i++) { if (canPlace(line, i)) { result[line] = i; //可以放置的情况下，就在该点放置棋子 place(line, i); if (line != n) { //如果该行不是最后一行，就继续搜索 search(line + 1); } else { //如果该行是最后一行，那么此时一定可以保证前面所有的棋子互不冲突，那么就输出解 resultNum++; if (resultNum <= 3) { printResult(); } } //一定要记着取消放置 unplace(line, i); } } } int main() { cin>>n; search(1); cout << resultNum; } ```