題目描述

52. N-Queens II

回溯法?

這道題與第51題是一樣的。51. N-Queens-CSDN博客

class Solution {int columns;  //從低位到高位起算，第i位為0表示棋盤第i列可以放置皇后，第i位為1表示棋盤第i列不能放置皇后//邊長為n的棋盤分別有2n-1條正斜線和反斜線。int diagnals1;//反斜線（從右上角到左下角）。第i位表示第i條反斜線能否放置皇后int diagnals2;//正斜線（從左上角到右下角）。含義同上int res = 0;
public:int totalNQueens(int n) {columns = 0;diagnals1 = 0;diagnals2 = 0;backtrack(n,0);return res;}void backtrack(int n,int row){if(row==n){res++;return;}for(int col = 0;col <n;col++){if(columns &(1<<col))continue;int diag1 = row+col;if(diagnals1 &(1<<diag1))continue;int diag2 = row-col+(n-1);if(diagnals2 &(1<<diag2))continue;columns |= (1<<col);diagnals1 |= (1<<diag1);diagnals2 |= (1<<diag2);backtrack(n,row+1);columns &= (~(1<<col));diagnals1 &= (~(1<<diag1));diagnals2 &= (~(1<<diag2)); }}
};