题意
求出含有
n
个皇后的所有的棋盘摆放方案
思路
经典的DFS + 回溯问题，使用
loc[i]
表示第
i
列的皇后在第几行，后面的就是DFS 回溯了，各大算法和数据结构的书中都有这种问题，就不再写思路了.
代码
class Solution {
public:
vector<vector<string>> solveNQueens(
int n) {
vector<int>loc;
for(
int i =
0; i < n; i++){
loc.push_back(-
1);
}
vector<vector<string> >ans;
DFS(loc,
0, n, ans);
return ans;
}
private:
void DFS(
vector<int>& loc,
int id,
int n,
vector<vector<string> >& ans){
if(id == n){
vector<string>temp;
for(
int i =
0; i < n; i++){
string s =
"";
for(
int j =
0; j < n; j++){
if(j == loc[i]){
s +=
"Q";
}
else{
s +=
".";
}
}
temp.push_back(s);
}
ans.push_back(temp);
return ;
}
for(
int i =
0; i < n; i++){
int flag =
0;
for(
int j =
0; j < id; j++){
if((loc[j] == i) || (id + i == loc[j] + j) || (i - loc[j] == id - j)){
flag =
1;
break;
}
}
if(flag)
continue;
loc[id] = i;
DFS(loc, id +
1, n, ans);
loc[id] = -
1;
}
}
};
