/*
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Subscribe to see which companies asked this question
*/
/*
解题思路：
深度遍历的典型题目，按行开始一层代表一行，当在某行的某个位置填上Q之后，还要验证一下是否符合，验证的标准是看看前面已经处理完的几行中，是否在当前列填了Q或者先前的Q与本行的Q在斜对角线上，如果出现任意一种情况都不合适。
*/
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
//把所有可能的情况都存起来
string s(n,'.');
vector<string> vec(n,s);
vector<vector<string>> res;
dfs(0,vec,res);
return res;
}
void dfs(int cur,vector<string>&vec,vector<vector<string>>&res){
if(cur==vec.size()){
res.push_back(vec);
return ;
}
for(int i=0;i<vec.size();i++){
if(isvalid(cur,i,vec)){
vec[cur][i]='Q';
dfs(cur+1,vec,res);
vec[cur][i]='.';
}
}
}
bool isvalid(int row,int col,vector<string>vec){
for(int i=0;i<row;i++){
for(int j=0;j<vec.size();j++){
if(vec[i][j]=='Q'){
if(j==col || abs(j-col)==abs(i-row))return false;
}
}
}
return true;
}
};