[Leetcode] n queens ii n皇后问题

Follow up for N-Queens problem.

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

题意：仅要求给出解的种数。

思路：这题是n queens的简化版。思路是一样的，可参见上题的解法。代码如下：

 1 class Solution 
 2 {
 3 public:
 4     int totalNQueens(int n) 
 5     {
 6         int resNum=0;
 7         vector<int> state(n,-1);
 8         helper(state,0,resNum);
 9         return resNum;    
10     }
11 
12     void helper(vector<int> &state,int row;int &resNum)
13     {
14         int n=state.size();
15         if(row==n)
16         {
17             resNum++;
18         }
19         else
20         {
21             for(int col=0;col<n;++col)
22             {
23                 if(isVaild(state,row,col))
24                 {
25                     state[row]=col;
26                     helper(state,row+1,resNum);
27                     state[row]=-1;
28                 }
29             }
30         }
31     }
32 
33     bool isVaild(vector<int> &state,int row,int col)
34     {
35         for(int i=0;i<row;++i)
36         {
37             if(state[i]==col||abs(row-i)==abs(col-state[i]))
38                 retrun false;
39         }
40         return true;
41     }
42 };

注：还可以使用位运算解决n皇后的问题。