###### tags: `LeetCode` `Recursion` `Hard` `DFS` `String`
# LeetCode #52 [N-Queens II](https://leetcode.com/problems/n-queens-ii/)
### (Hard)

n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，並且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回 n 皇后問題 不同的解決方案的數量。


---

與 [#51](https://hackmd.io/1dNKhOB5Sa-TsMS6p0DnMQ) 幾乎一樣, 差別是只要回傳所有組合的數量而非所有的組合, 因此只要符合終止條件時, 讓計數器+1, 最後再回傳計數器即可。

---

class Solution {
public:
    int count=0;
    int totalNQueens(int n) {
        vector<string> board(n, string(n,'.'));
        dfs(board, 0, n);
        return count;
    }
    void dfs(vector<string>& board, int row, const int& n){
        if(row==n)++count;
        for(int col=0;col<n;col++){
            if(!isvalid(board, row, col, n))continue;
            board[row][col]='Q';
            dfs(board, row+1, n);
            board[row][col]='.';
        }
    }
    bool isvalid(vector<string>& board, int row, int col, const int& n){
        for(int i=0;i<row;i++)if(board[i][col]=='Q')return false;//直的
        for(int i=row-1, j=col-1;i>=0&&j>=0;i--,j--)if(board[i][j]=='Q')return false;//左上
        for(int i=row-1, j=col+1;i>=0&&j<n;i--,j++)if(board[i][j]=='Q')return false;//右上
        return true;
    }
};