您的位置: 首页  >  文章  >  Leetcode:51.N皇后&&Leetcode:52. N皇后II

Leetcode:51.N皇后&&Leetcode:52. N皇后II

分类: 文章 • 2024-07-04 09:09:10

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

Leetcode:51.N皇后&&Leetcode:52. N皇后II

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

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

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

示例:

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

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

解题思路51：

皇后问题是经典的回溯算法，相信大家也在不少的数据结构，算法书中看到过，若果看过书并且理解了，这个只能算个简单题。大致的步骤如下：

1. 每一行肯定只能放一个皇后，所以将N个皇后的位置初始化放置在每一行的第一列。

2. 不考虑回溯的话，理论上需要列举所有情况，由于N的个数未知，所以采用递归。

3. 每确定某一行的皇后位置即可确定下一行的皇后位置。确定当前行的皇后需要保证与之前已经放置的所有皇后都不冲突，很显     然需要写一个判断两个皇后是否兼容的函数（bool isOK(pair<int,int>a,pair<int,int>b);）。

4.如果在某一行发现，这一行都没有可行的位置，那么就不用继续判断下一行，回溯到上一步。（第4步是皇后问题的核心思想）。这是提速的关键步骤，不然基本是超时。

5. 如果在最后一行发现可行的位置，将当前的访问路径写入结果即可。

注意事项：

解题思路52：

思路一致，只不过输出形式不一样而已。

皇后问题的基本解法就是以上5个步骤，本题而言容易出错的就是n的范围，注意它说的是整数n，一定要注意细节，可能是0,严格来讲还可能是个负值。

Leetcode:51.N皇后&&Leetcode:52. N皇后II

51：C++
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        if (n <= 0) return vector<vector<string>>();
        if (n == 1) return vector<vector<string>>(1, vector<string>(1, "Q"));
        N = n;
        Queens = vector<int>(n, 0);//n个皇后的初始位置都在每一行的第一个
        DFS(0);
        //根据每一个road，输出一个相应的字符串（二维）
        vector<string>MAP;
        vector<vector<string>> MAPs;
        for (int i = 1; i <= int(res.size()); i++) {
            for (int j = 1; j <= N; j++) {
                MAP.push_back(int2str(res[i - 1][j - 1], N));
            }
            MAPs.push_back(MAP);
            MAP.clear();
        }
        return MAPs;
    }
private:
    void DFS(int num) {
        int i,j;
        pair<int, int> a, b;
        if (num == 0 ) {
            for (i = 0; i < N; i++) {
                DFS(num + 1);
                Queens[num] ++;
            }
            return;
        }
        if (num > 0&&num<N-1) {
            //找到所有与前面皇后兼容的点，如果没有return
            for (i = 0; i < N; i++) {
                Queens[num] = i;
                a=pair<int,int>(num, Queens[num]);
                //判断第num个皇后在第Queens[num]列时，与前面皇后的兼容情况
                bool sgn = true;
                for (j = 0; j < num; j++) {
                    b.first = j;
                    b.second = Queens[j];
                    if (!isOK(a, b)) { sgn = false; break; }
                }
                if (sgn == true) DFS(num + 1);
            }
            return;
        }
        if (num == N - 1) {//达到最后一层
           //判断与前面所有皇后是否兼容
            for (i = 0; i < N; i++) {
                Queens[num] = i;
                a = pair<int, int>(num, Queens[num]);
                //判断第num个皇后在第Queens[num]列时，与前面皇后的兼容情况
                bool sgn = true;
                for (j = 0; j < num; j++) {
                    b.first = j;
                    b.second = Queens[j];
                    if (!isOK(a, b)) { sgn = false; break; }
                }
                if (sgn == true) {
                    vector<int> Road;
                    for (j = 1; j <= N; j++) {
                        Road.push_back(Queens[j - 1]);
                    }
                    res.push_back(Road);
                }
            }
            return;
        }
    }
    bool isOK(pair<int, int> a, pair<int, int> b) {//判断两个皇后的位置是否兼容
        if (a.first == b.first) return false;
        if (a.second == b.second) return false;
        if (abs(a.first - b.first) == abs(a.second - b.second)) return false;
        return true;
    }
    string int2str(int pos, int N) {
        return string(pos, '.') + string(1, 'Q') + string(N - (pos + 1), '.');
    }
private:
    int N;
    vector<vector<int>> res;
    vector<int> Queens;
};

Leetcode:51.N皇后&&Leetcode:52. N皇后II

52:C++代码
class Solution52 {
public:
    int totalNQueens(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        solveNQueens(n);
        return int(res.size());
    }
    vector<vector<string>> solveNQueens(int n) {
        if (n <= 0) return vector<vector<string>>();
        if (n == 1) return vector<vector<string>>(1, vector<string>(1, "Q"));
        N = n;
        Queens = vector<int>(n, 0);//n个皇后的初始位置都在每一行的第一个
        DFS(0);
        //根据每一个road，输出一个相应的字符串（二维）
        vector<string>MAP;
        vector<vector<string>> MAPs;
        for (int i = 1; i <= int(res.size()); i++) {
            for (int j = 1; j <= N; j++) {
                MAP.push_back(int2str(res[i - 1][j - 1], N));
            }
            MAPs.push_back(MAP);
            MAP.clear();
        }
        return MAPs;
    }
private:
    void DFS(int num) {
        int i,j;
        pair<int, int> a, b;
        if (num == 0 ) {
            for (i = 0; i < N; i++) {
                DFS(num + 1);
                Queens[num] ++;
            }
            return;
        }
        if (num > 0&&num<N-1) {
            //找到所有与前面皇后兼容的点，如果没有return
            for (i = 0; i < N; i++) {
                Queens[num] = i;
                a=pair<int,int>(num, Queens[num]);
                //判断第num个皇后在第Queens[num]列时，与前面皇后的兼容情况
                bool sgn = true;
                for (j = 0; j < num; j++) {
                    b.first = j;
                    b.second = Queens[j];
                    if (!isOK(a, b)) { sgn = false; break; }
                }
                if (sgn == true) DFS(num + 1);
            }
            return;
        }
        if (num == N - 1) {//达到最后一层
           //判断与前面所有皇后是否兼容
            for (i = 0; i < N; i++) {
                Queens[num] = i;
                a = pair<int, int>(num, Queens[num]);
                //判断第num个皇后在第Queens[num]列时，与前面皇后的兼容情况
                bool sgn = true;
                for (j = 0; j < num; j++) {
                    b.first = j;
                    b.second = Queens[j];
                    if (!isOK(a, b)) { sgn = false; break; }
                }
                if (sgn == true) {
                    vector<int> Road;
                    for (j = 1; j <= N; j++) {
                        Road.push_back(Queens[j - 1]);
                    }
                    res.push_back(Road);
                }
            }
            return;
        }
    }
    bool isOK(pair<int, int> a, pair<int, int> b) {//判断两个皇后的位置是否兼容
        if (a.first == b.first) return false;
        if (a.second == b.second) return false;
        if (abs(a.first - b.first) == abs(a.second - b.second)) return false;
        return true;
    }
    string int2str(int pos, int N) {
        return string(pos, '.') + string(1, 'Q') + string(N - (pos + 1), '.');
    }
private:
    int N;
    vector<vector<int>> res;
    vector<int> Queens;
};

 

相关推荐