N Queens II

LeetCode #52

Description:

Follow up for N-Queens problem.

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
            }
        }
    }
};