class Solution { public: int totalNQueens(int n) { //initialize chessboard vector<vector<bool>> boardconf; vector<bool> orig_row; orig_row.assign(n,false); boardconf.assign(n,orig_row); int totalNum = 0; for(int j = 0; j < n; j++){ totalNum+= NQueens(boardconf,0,j,n); } return totalNum; } int NQueens(vector<vector<bool>> cb, int i, int j,int n){ if(i == n-1){ if(not_attack(cb,i,j,n)) return 1; else return 0; }else{ if(not_attack(cb,i,j,n)){ int tmp = 0; for(int k = 0; k < n; k++){ tmp = NQueens(cb,i+1,k,n); } return tmp; }else return 0; } } bool not_attack(vector<vector<bool>> cb, int row, int col,int n){ int i = 0; while(i < row){ if(cb[i][col]) return false; i++; } i = row - 1; int j = col - 1; while(i >= 0 && j >= 0){ if(cb[i][j]) return false; i--; j--; } i = row - 1; j = col + 1; while(i >= 0 && j < n){ if(cb[i][j]) return false; i--; j++; } return true; } };
上面的答案是我提交的第一个版本，提交后显示“Time Limit Exceed”。"Time Limit Exceed" 一般意味着算法复杂度太高，所以我首先检查是否是所用递归方法的问题。我看了一些网上关于此题的解答，都是递归的思路，所以排除了递归是造成超时的主要原因。继而我对所用数据结构分析，上面的解法要维护一个n*n的chessboad configuration，并且递归每深入一层都要copy上一层的chessboard configuration。这是很耗时间的。其实在判断某个位置是否可以放Queen时，我们并不需要维护一个完整的chessboard，因为我们只用判断(i,j)所处的主对角线、反对角线、列是否已经有Queen，所以我们可以用三个数组分别记录对应的主对角线、反对角线、列是否已经有Queen即可。
不过里面有个小trick需要注意，当i层的递归结束之后，我们需要把记录主对角线、反对角线、列的三个数组复原。
class Solution { public: int totalNQueens(int n) { this->columns = vector<bool>(n,false); this->main_diag = vector<bool>(2*n-1,false); this->anti_diag = vector<bool>(2*n-1,false); int totalNum = 0; for(int j = 0; j < n; j++){ totalNum+= NQueens(0,j,n); } return totalNum; } int NQueens(int i, int j,int n){ if(i == n-1){ if(!(columns[j]||main_diag[i-j+n-1]||anti_diag[i+j])) return 1; else return 0; }else{ if(!(columns[j]||main_diag[i-j+n-1]||anti_diag[i+j])){ columns[j]=true; main_diag[i-j+n-1]=true; anti_diag[i+j]=true; int tmp = 0; for(int k = 0; k < n; k++){ tmp += NQueens(i+1,k,n); } columns[j]=false; main_diag[i-j+n-1]=false; anti_diag[i+j]=false; return tmp; }else return 0; } } private: vector<bool> columns; vector<bool> main_diag; vector<bool> anti_diag; };
Leetcode: N-Queens II C++,布布扣,bubuko.com
原文：http://www.cnblogs.com/Kai-Xing/p/3884762.html