按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
- 这道题目也是回溯题目,创建一个 vector<vector<string>> results; 用来存放一组结果,使用vector<string> result(n, string(n, ‘.’)); 来模拟一个棋盘
- 每次向棋盘的一行添加一个 皇后,在添加之前,需要判断添加的位置是否是有效位置, 判断是否是有效位置,需要一个函数来判断 这个位置 行、列、左右对斜线 都不能有 皇后,因为添加操作时按行进行,所以当前行以及之后的行时肯定没由皇后的,因此可以对判断进行剪枝操作。
- 剪枝操作,只需判断 所在列,之前的行是否存在 皇后,右上斜线 和左上斜线是否存在 皇后
- 在判断完成后,如果这个位置有效,则在这个位置添加皇后,并进行递归,对下一行添加
代码如下:
class Solution {
private:
vector<vector<string>> results;
public:
bool isVaild(int row, int col, int n, vector<string>& result){
for(int i = 0; i < row; i++){
if(result[i][col] == 'Q'){
return false;
}
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
if(result[i][j] == 'Q'){
return false;
}
}
for(int i = row - 1, j = col - 1; i >=0 && j >=0; i--, j--){
if(result[i][j] == 'Q'){
return false;
}
}
return true;
}
void backtracking(int n, int curNum, vector<string>& result){
if(curNum == n){
results.push_back(result);
return;
}
for(int i = 0; i < n; i++){
if(isVaild(curNum, i, n, result)){
result[curNum][i] = 'Q';
backtracking(n, curNum + 1, result);
result[curNum][i] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> result(n, string(n, '.'));
backtracking(n, 0, result);
return results;
}
};
标签:return,int,力扣,curNum,vector,result,皇后
From: https://blog.csdn.net/why_12134/article/details/139776516