【第58题】回溯算法三连发（四）：[USACO1.5]八皇后 ，切到回溯

题目

题目原文请移步下面的链接

• https://www.luogu.com.cn/problem/P1219
  • 参考题解：https://www.luogu.com.cn/problem/solution/P1219
• 标签：搜索 、 深搜 、 回溯

题解

• 第二个是回溯法，l_diag是左斜线（/)，另一个反之，大体思路不变，比较难的就在对角线上（本蒟蒻搁着卡半天）
  • 我们知道，对角线上他索引的和差是有定值的,因为他左斜线移动时上一个放大，另一个就缩小，右斜线同时放大缩小，所以左斜线他的和不变，右边斜线差不变，但我们又发现它的差搞不好就是个负数了（例如（2,5））所以直接给他所有点无差别往上加n它的差值再大也大不过n嘛
• 官方题解
  • 题解大家可移步看这里，很多童鞋写了各种解法
  • https://www.luogu.com.cn/problem/solution/P1219

代码

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;
#define endl 'n';

void print(int n, int &ans, vector<int> &row) {
    int i;
      ans;
    if (ans <= 3) {
        for (i = 1; i <= n;   i) {
            cout << row[i] << " ";
        }
        cout << endl;
    }
}

void dfs(int a, int n, int &ans, vector<int> &row, vector<int> &col, vector<int> &l_diag, vector<int> &r_diag) {
    for (int i = 1; i <= n;   i)
        if (col[i] == 0 && l_diag[a   i] == 0 && r_diag[a - i   n] == 0) {
            row[a] = i;
            col[i] = 1;
            l_diag[a   i] = 1;
            r_diag[a - i   n] = 1;
            if (a == n) {
                print(n, ans, row);
            } else {
                dfs(a   1, n, ans, row, col, l_diag, r_diag);
            }
            col[i] = 0;
            l_diag[a   i] = 0;
            r_diag[a - i   n] = 0;
        }
}

void happy_coder() {
    int n;
    cin >> n;
    vector<int> row(50);
    vector<int> col(50);
    vector<int> l_diag(50);
    vector<int> r_diag(50);
    int ans = 0;
    dfs(1, n, ans, row, col, l_diag, r_diag);
    cout << ans;
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    //best_coder();

    // 最优解
    happy_coder();

    // 返回
    return 0;
}

int vector 搜索 算法 效率

0 人点赞