LintCode(34) N-Queens II

Follow up for N-Queens problem.

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

Have you met this question in a real interview? 

Yes

Example

For n=4, there are 2 distinct solutions.

承接上题，变了个花样。。。不过可以看出这种题目的规律。。。其实很羞愧的一直在想dp的事情，貌似dp是解不出的。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

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> solution; int res=0; dfs(solution, res, n); return res; } void dfs(vector<int>& solution, int& res, int n){ if (solution.size()==n) res++; for (int i=0; i<n; i++){ if (!isValid(solution, i)) continue; solution.push_back(i); dfs(solution, res, n); solution.pop_back(); } } bool isValid(vector<int>& solution, int ind){ if (solution.empty()) return true; int n=solution.size(); for (int i=0; i<n; i++){ if (solution[i]==ind) return false; if (solution[i]+i==ind+n) return false; if (i-solution[i] == n-ind) return false; } return true; } };