0051. N皇后

// 循环遍历，学到了vector<vector<string> >的初始化
1051. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。



上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
class Solution {
public:        
    vector<vector<int> > pos;
    vector<int> tmp;//没有这句会越界
    vector<vector<string> > solveNQueens(int n){
        tmp = vector<int>(n, 0); 
        Queen(0, n);
        vector<vector<string> > ans(pos.size(), vector<string>(n, string(n, '.')));
        for(int k=0; k<pos.size(); k++){
            for(int i=0; i<n; i++){
                ans[k][i][pos[k][i]] = 'Q';
            }
        }
        return ans;
    }
    void Queen(int k, const int& n){
        if(k == n){
            pos.push_back(tmp);
            return;
        }
        for(int i=0; i<n; i++){
            int j;
            for(j=0; j<k; j++){
                if(tmp[j]==i || abs(i-tmp[j])==abs(k-j))
                    break;
            }
            if(j == k){
                tmp[k] = i;
                Queen(k+1, n);
            }
        }
    }
};