本文共 1578 字，大约阅读时间需要 5 分钟。

Follow up for N-Queens problem.

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

思路：此题虽然是N皇后问题的变体，但还是可以用N皇后的思路去解决，只是用了一个set来存储合法的皇后

bool isNQueens(vector
   
    & res){    for (int i = 0; i < res.size(); i++){        for (int j = i + 1; j < res.size(); j++){            if (i - j == res[i] - res[j] || i - j == res[j] - res[i])return false;        }    }    return true;}void dfs_SolveNQueens(vector
    
     & res, int pos, set
     
      
       >& tt){    if (pos == res.size()){        if (isNQueens(res)){            tt.insert(res);        }        return;    }    for (int i = pos; i < res.size(); i++){        swap(res[i], res[pos]);        dfs_SolveNQueens(res, pos + 1, tt);        swap(res[i], res[pos]);    }}int totalNQueens(int n){    if (n == 0)return 0;    vector
       
         temp;    for (int i = 0; i < n; i++)temp.push_back(i);    set
        
         
          > res; dfs_SolveNQueens(temp, 0, res); return res.size();}
         
        
       
      
     
    
   

思路1可能有重复的计算量

bool safe(vector
   
    & res, int c){    for (int i = 0; i < c; i++){        if (res[i] == res[c] || abs(res[i] - res[c] == abs(i - c)))            return false;    }    return true;}void dfs_SloveNQueens(int &cnt, vector
    
     & res, int n, int c){    if (c == n){        cnt++;        return;    }    for (res[c] = 0; res[c] < n; res[c]++){        if (safe(res, c))dfs_SloveNQueens(cnt, res, n, c + 1);    }}int totalNQueens(int n){    vector
     
       res(n);    int cnt = 0;    dfs_SloveNQueens(cnt, res, n, 0);    return cnt;}