N-Queens II

N-Queens II

 Follow up for N-Queens problem.

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

------------------------ thinking ---------------------------------
https://oj.leetcode.com/discuss/22319/2ms-c-solution-by-keeping-track-of-diagonals-rows

It's better to recode this problem by using the other people's faster solutions!!!!
The different ways to store marking info!!!!
https://oj.leetcode.com/discuss/22319/2ms-c-solution-by-keeping-track-of-diagonals-rows
-------------------------- codes -----------------------------------
class Solution {
public:
    int totalNQueens(int n) {
        int num = 0;
        vector<int> marker(n, 0);
        puzzleHelper(num, marker, 0, n);
        return num;
    }
    void puzzleHelper(int &num, vector<int>marker, int row, int n) {
        if (row == n) {
            num += 1;
        }
        for (int try_col = 0; try_col < n; try_col++) {
            if (isSafe(marker, row, try_col)) {
                marker[row] = try_col;
                puzzleHelper(num, marker, row+1, n);
            }
        }
    }
    bool isSafe(vector<int> marker, int row, int col) {
        for (int cur_row = row-1, ldia=col-1, rdia=col+1; cur_row>=0; cur_row--, ldia--, rdia++) {
            if (marker[cur_row] == col || marker[cur_row] == ldia || marker[cur_row] == rdia) {
                return false;
            }
        }
        return true;
    }
};

------------------------------------- codes --------------------------------
class Solution {
bool *cols, *ldiags, *rdiags;
int out;
public:
    int totalNQueens(int n) {
        bool temp1[n] = {0}, temp2[2*n] = {0}, temp3[2*n] = {0};
        cols = &temp1[0]; ldiags = &temp2[0]; rdiags = &temp3[0];
        out = 0;
        helper(0, n);
        return out;
    }
    void helper(int r, int n){
        if (r==n){
            out++;
            return;
        }
        int i;
        for (i=0;i<n;i++){
            if (cols[i]) continue;
            if (ldiags[r-i+n]) continue;
            if (rdiags[r+i]) continue;

            cols[i] = 1;
            ldiags[r-i+n]=1;
            rdiags[r+i]=1;

            helper(r+1, n);

            cols[i] = 0;
            ldiags[r-i+n]=0;
            rdiags[r+i]=0;
        }

    }
};