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

小码匠

发布于 2023-08-31 15:06:05

1690

文章被收录于专栏：小码匠和老码农小码匠和老码农

题目

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

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

代码

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除

int