刷代码随想录有感（79）：回溯算法——N皇后问题

本文主要是介绍刷代码随想录有感（79）：回溯算法——N皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题干:

代码：

class Solution {
public:vector<vector<string>> res;void backtracking(vector<string>& chessboard, int n, int row){if(row == n){res.push_back(chessboard);return;}for(int col = 0; col < n; col++){if(isvalid(chessboard, n, row, col)){chessboard[row][col] = 'Q';backtracking(chessboard, n, row + 1);chessboard[row][col] = '.';}}}bool isvalid(vector<string> chessboard, int n, int row, int col){for(int i = row - 1; i >= 0; i--){if(chessboard[i][col] == 'Q')return false;//同一列上不能有}for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if(chessboard[i][j] == 'Q')return false;//左上对角不能有}for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){if(chessboard[i][j] == 'Q')return false;//右上对角不能有}return  true;}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backtracking(chessboard, n, 0);return res;}
};

注意：开始行和列为了方便都设为0

vector<string> chessboard(n, string(n, '.'));是建立二维字符串棋盘的方法，表示创建一个包含 n 个字符串的容器，其中每个字符串的长度也是 n，并且所有字符1都初始化为 '.'，表示空白位置。

合法性判断：

 

这篇关于刷代码随想录有感（79）：回溯算法——N皇后问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---