N-Queens II

Follow up for N-Queens problem.

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

http://www.lintcode.com/en/problem/n-queens-ii/

Solution

不记录中间结果，只输出解的个数。

class Solution {
public:
    /**
     * Calculate the total number of distinct N-Queen solutions.
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    int totalNQueens(int n) {
        // write your code here
        if(n==0) return 0;
        vector<int> state (n, -1);
        int num=0;
        dfs(0, state, num);
        return num;
    }
    void dfs(int row, vector<int> &state, int &num) {
        int n = state.size();
        if(row == n) {//output result
            num++;
            return;
        }
        for(int col=0; col<n; col++) {
            if(isSafe(state, row, col)) {
                state[row] = col;
                dfs(row+1, state, num);
                state[row] = -1;
            }
        }
    }
    bool isSafe(vector<int> &state, int row, int col) {
        for(int i=0; i<row; i++) {
            if(state[i] == col || row-i==abs(col-state[i])) {
                return false;
            }
        }
        return true;
    }
};