题解 | #八皇后#

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

int res[93]; //存放结果的数组
int chessboard[8][8]; //棋盘 1表示有皇后
int pos[8]; //第i行的皇后放在pos[i]列
int index = 1;

/**
    row 行
    col 列
    判断chessboard[row][col]能不能放皇后
    能则返回true
*/
bool isvalid(int row, int col) {
  
    for (int i = 0; i < 8; i++) { //依次遍历每一行
        //如果当前列有皇后  或者   斜着的方向有皇后   则不行
        if (pos[i] == col || abs(pos[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

/**
    row 现在到了第几行
    seq 当前的输出是什么
*/
void queen(int row, int seq) {
    if (row == 8) { //已经超出棋盘了，保存结果
        res[index++] = seq;
        return;
    }
    //在第row行的每列进行查看，看能不能放皇后
    for (int i = 0; i < 8; i++) {
        if (isvalid(row, i)) {
            chessboard[row][i] = 1;
            pos[row] = i;
            //接着看下一行，加入对应的序列号
		    //这个i+1很关键别忘了从1开始的
            queen(row + 1, seq * 10 + i + 1);
            //回溯
            chessboard[row][i] = 0;
            pos[row] = 100;
        }
    }
    return;
}


int main() {
    int b;
    while (scanf("%d", &b) != EOF) { //要求第几个字符串
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                chessboard[i][j] = 0;  //初始化棋盘
            }
        }
	  
	  //随便找个值初始化pos数组，但注意这里最好不要为0,1，-1之类的，最好大一点
	  //防止在isvalid函数中abs计算有误会
        for (int i = 0; i < 8; i++) { 
            pos[i] = 100;
        }

        queen(0, 0); //从第0行开始， 初始序列为0

        printf("%d\n", res[b]);
    }

}

无语了，测试用例说我超时，但是确可以直接提交。。。。。。