LeetCode刷题--- N 皇后

2023-12-28 00:21:13

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法

?http://t.csdnimg.cn/yUl2I? ?

【C++】? ??

http://t.csdnimg.cn/6AbpV

数据结构与算法

???????http://t.csdnimg.cn/hKh2l


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的 ?

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


N 皇后

题目链接:N 皇后

题目

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

解法

算法原理思路讲解?

算法思路
  1. ?先,我们在第??放置第?个皇后,然后遍历棋盘的第??,在可?的位置放置第?个皇后,然后再遍历第三?,在可?的位置放置第三个皇后,以此类推,直到放置了 n 个皇后为?。
  2. 我们需要??个数组来记录每??放置的皇后的列数。在每??中,我们尝试放置?个皇后,并检查是否会和前?已经放置的皇后冲突。如果没有冲突,我们就继续递归地放置下??的皇后,直到所有的皇后都放置完毕,然后把这个?案记录下来。
  3. 在检查皇后是否冲突时,我们可以??个数组来记录每?列是否已经放置了皇后,并检查当前要放置的皇后是否会和已经放置的皇后冲突。对于对?线,我们可以?两个数组来记录从左上?到右下?的每?条对?线上是否已经放置了皇后,以及从右上?到左下?的每?条对?线上是否已经放置了皇后。
对于对?线是否冲突的判断可以通过以下流程解决
  • 从左上到右下:相同对?线的?列之差加 n (防止?列之差为负数)相同;
  • 从右上到左下:相同对?线的?列之和相同。
因此,我们需要创建?于存储解决?案的?维字符串数组 ret ? ,?于存储每个皇后的位置的
?维整数数组 path ? ,以及?于记录每?列和对?线上是否已经有皇后的布尔型数组。
(1)全局变量
    bool checkCol[10], checkDig1[20], checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int N;
  • ret(存储解决?案的?维字符串数组 ?)
  • path(?于存储每个皇后的位置的?维整数数组)
  • N(n 的大小)
  • checkCol(记录每?列上是否已经有皇后的布尔型数组
  • checkDig1(记录对?线上的主线是否已经有皇后的布尔型数组
  • checkDig2(记录对?线上的副线是否已经有皇后的布尔型数组

(2)设计递归函数

void dfs(int row);
  • 参数:row(表示现在要处理的行数);
  • 返回值:无;
  • 函数作用:在当前?放??个不发?冲突的皇后,查找所有可?的?案使得放置 n 个皇后后不发?冲突。
递归函数流程如下
  1. 递归结束条件:如果 row 等于 n ,则表?已经找到?组解决?案,此时将每个皇后的位置存储到字符串数组 ret?中,并将 path?存储到 ret?数组中,然后返回;
  2. 枚举当前?的每?列,判断该列、两个对?线上是否已经有皇后:
    1. 如果有皇后,则继续枚举下?列;
    2. 否则,在该位置放置皇后,并将 checkCol[10], checkDig1[20], checkDig2[20];对应的位置,设为 true ,表?该列和对?线上已经有皇后:
  3. 递归调? dfs 函数,搜索下??的皇后位置。如果该?案递归结束,则在回溯时需要将checkCol[10], checkDig1[20], checkDig2[20]; 对应的位置设为 false ,然后继续枚举下?列;

以上思路讲解完毕,大家可以自己做一下了


代码实现

class Solution {
public:
    bool checkCol[10], checkDig1[20], checkDig2[20];
    vector<vector<string>> ret;
    vector<string> path;
    int N;

    void dfs(int row)
    {
        if (row == N)
        {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < N; col++) // 尝试在这??放皇后
        {
            // 剪枝
            if (!checkCol[col] && !checkDig1[row - col + N] && !checkDig2[row +col])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + N] = checkDig2[row +col] = true;

                dfs(row + 1);

                path[row][col] = '.';                // 恢复现场
                checkCol[col] = checkDig1[row - col + N] = checkDig2[row +col] = false;
            }

        }
    }
    vector<vector<string>> solveNQueens(int n) 
    {
        N = n;
        path.resize(n);
        for (int i = 0; i < n; i++)
        {
            path[i].append(n, '.');
        }

        dfs(0);
        return ret;
    }
};

文章来源:https://blog.csdn.net/weixin_74268082/article/details/135237029
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。