LeetCode #52

# Description:

Now, instead outputting board configurations, return the total number of distinct solutions.

## Example:

``````Note
``````

# Idea:

N Queens与N Queens II很类似，II需要把结果存下来，而不是count增加。

Mark的是occupy哪列和哪些对角线，Backtrack也是这些。II的时候，还要存暂时的结果，不过不需要backtrack temporary result.

# Code:

``````class Solution {
public:
int totalNQueens(int n) {
vector<bool> column_occupy(n, false);
vector<bool> diag_occupy(2*n-1, false);
vector<bool> anti_diag_occupy(2*n-1, false);
int count=0;
DFS(0, count, column_occupy, diag_occupy, anti_diag_occupy);
return count;
}

void DFS(int row, int& count, vector<bool>& column_o, vector<bool>& diag_o, vector<bool>& anti_diag_o){
int N=column_o.size();
if(row==N){
count++;
return;
}

// j is column index
for(int j=0; j<N; ++j){
if(!column_o[j] && !diag_o[row+j] && !anti_diag_o[N-1-row+j]){
column_o[j]=diag_o[row+j]=anti_diag_o[N-1-row+j]=true; // Mark
DFS(row+1, count, column_o, diag_o, anti_diag_o);
column_o[j]=diag_o[row+j]=anti_diag_o[N-1-row+j]=false; // Backtrack
}
}
}
};
``````