LeetCode N皇后(回溯)

SakuraTears

发布于 2022-01-13 11:40:08

2660

发布于 2022-01-13 11:40:08

文章被收录于专栏：从零开始的Code生活

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

上图为 8 皇后问题的一种解法。

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

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

示例：

输入：4 输出：[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],

["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/n-queens

经典回溯+递归问题，当发现这种情况不行时就回溯到之前的点。

代码：

class Solution {
public:
    int col[12] = {};//将合适的皇后行数放入数组中
    vector<vector<string>> arr;
    vector<string> brr;
    char crr[100][100];
    int cnumber = 0;
    int num, number = 0, jud = 0, tot = 0;
    bool check(int c, int r)
    {
        int i = 0;
        for (i = 0; i < r; i++)
        {
            if (col[i] == c || (abs(col[i] - c) == abs(i - r)))
                return false;
        }
        return true;
    }

    void DFS(int r)
    {
        if (r == num)
        {
            string str = "";
            brr.clear();
            for (int j = 0; j < num; j++)
            {
                str = "";
                
                for (int i = 0; i < num; i++)
                {
                    if (crr[j][i] == 'Q')
                        str += "Q";
                    else
                        str += ".";
                }
                brr.push_back(str);
            }
            arr.push_back(brr);
            return;
        }
        for (int c = 0; c < num; c++)
        {
            if (check(c, r) == true)
            {
                col[r] = c;
                int i = 0;
                while (i < num)
                {
                    if (i == c)
                    {
                        crr[r][i] = 'Q';
                    }
                    else
                        crr[r][i] = '.';
                    i++;
                }
                DFS(r + 1);
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        num = n;
        DFS(0);
        return arr;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020年10月16日，如有侵权请联系 cloudcommunity@tencent.com 删除

网络安全