leetcode 51. N 皇后-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 51. N 皇后。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.24

leetcode 51. N 皇后,leetcode专栏,leetcode,算法,职场和发展,数据结构,c++

回溯经典应用“N皇后”问题。本题依旧是利用回溯来做，将棋盘是放在一个vector<string>数组里面，棋盘的行数代表树的高度，棋盘的列数代表树的宽度。还需要定义一个辅助函数valid用于判断当前棋盘符不符合条件。

下面上代码：

class Solution {
public:
    vector<vector<string>> ans;
    bool valid(int row,int col,int n, vector<string>&chessboard)
    {
        //检查上方
        for(int i=0; i<row; 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;
    }
    void backtrack(int n,int row,vector<string>&chessboard)
    {
        //中止条件
        if(row == n)
        {
            ans.push_back(chessboard);
            return;
        }
        for(int col=0; col<n; col++)
        {
            if(valid(row,col,n,chessboard))
            {
                chessboard[row][col]='Q';
                backtrack(n,row+1,chessboard);
                chessboard[row][col]='.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));//初始化棋盘为全"."
        backtrack(n,0,chessboard);
        return ans;
    }
};

ps：由于递归是从上往下、每行只会放一个皇后，所以valid函数不需要检查行方向和下方，只需要检查上、左上、右上方向即可。文章来源地址https://www.toymoban.com/news/detail-610202.html

到了这里，关于leetcode 51. N 皇后的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！