leetcode——第51题——N皇后

题目:
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位

/*
复习一下回溯算法的模板:

void backtracking(参数)
{
    if(终止条件)
    {
        存放结果;
        return
    }
    for(选择:本层集合元素(树中节点孩子的数量就是集合的大小))
    {
        处理节点;
        backtracking(路径,选择列表);   // 递归
        回溯,撤销处理结果
    }
}
*/
class Solution {
private:
    vector<vector<string>> result;
    // 验证是否合法的函数 1、不能同行   2、不能同列     3、不能同斜线(45度和135度)
    // 代码为什么不在同行搜索是否有皇后呢???
    // 因为在单层搜索的过程中,每一层递归,只会选for循环(也就是同一行)里的一个元素,所以不用去重了。
    bool isValid(int row, int col, vector<string>& chessboard, int n)
    {
        int count = 0;
        // 检查列,相当于一个剪枝操作
        for(int i = 0; i < row; i++)
        {
            // 遍历这一列的每一行
            if(chessboard[i][col] == 'Q')
            {
                return false;
            }
        }
        // 检查 左上角 135度方向 是否有皇后
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--)
        {
            if(chessboard[i][j] == 'Q')
            {
                return false;
            }
        }
        // 检查 右上角 45度方向 是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if(chessboard[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    }


    // row 代表行数
    void backtracking(int n, int row, vector<string>& chessboard)
    {
        // 终止条件: 当递归到棋盘最底层,也就是叶子节点的时候,就可以收集结果并返回了
        if(row == n)
        {
            result.push_back(chessboard);
            return;
        }
        // 单层搜索的逻辑,注意递归的深度就是 row 控制棋盘的行,每一层里的for循环的 col 控制棋盘的列
        // 一个行数,一个列数,就可以确定皇后放置的位置,且每一次都是从0开始的
        for(int col = 0; col < n; col++)
        {
 // 注意这个验证是否合法的函数,这个也写得很妙,把需要的信息都当参数传进来,合法后才放入 chessboard
            // 如果不合法,直接下一列计算
            if(isValid(row, col, chessboard, n))
            {
                chessboard[row][col] = 'Q';  // 放置皇后
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';     // 回溯,撤销皇后
            }
        }
    }


public:
    vector<vector<string>> solveNQueens(int n) 
    {
        // 把整个棋盘都初始化为  .  的操作,也真是没有想到的一个点,这样便于后面做各种处理
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));   // 好赞
        backtracking(n, 0, chessboard);
        return result;
    }
};
上一篇:一个实战来了解学习稀疏数组


下一篇:C语言实现三子棋游戏