洛谷p1219 八皇后

2023-12-26 22:20:32

一道 d f s + dfs+ dfs+剪枝回溯的板子题,值得注意的是如何控制行,两条对角线都只存在一个数
题目链接

题目大意

给定正整数 n n n,使形成 n ? n n*n n?n的棋盘,有 n n n个棋子被放置其上,需要满足每行每列有且仅有 1 1 1个,每条对角线至多 1 1 1个,打印字典顺序三种摆棋方式和方案总数,摆棋方式如下
e g . eg. eg. 246135 2 4 6 1 3 5 246135,表示第一行的第二列有一个棋子,第二行的第四列有一个棋子,等

思路

显然是个 d f s dfs dfs,从第一行开始搜索,每一行从第一个位置开始判断,如果条件满足存进去,然后继续搜索下一行,如果不满足下一个位置,如果超过总列数就判断打印次数小于3就打印方案
因为本题实际输出的是路径,所以我们需要记录后剪枝,把选择过的去除

ACcode

#include<bits/stdc++.h>

using namespace std;

int ans, n;
const int M = 100;
int a[M], b[M], c[M], d[M];//存数,行,两条对角线

void print() {
    if (ans < 3) {
        for (int i = 1;i <= n;i++)cout << a[i] << ' ';
        cout << '\n';
    }
    ans++;
}

void dfs(int x) {
    if (x > n) {
        print();
        return;
    }
    for (int j = 1;j <= n;j++) {
        if (!b[j] && !c[x + j] && !d[x - j + n]) {
            a[x] = j;
            b[j] = 1;
            c[x + j] = 1;
            d[x - j + n] = 1;
            dfs(x + 1);
            b[j] = 0;
            c[x + j] = 0;
            d[x - j + n] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    ans = 0;//种类数
    dfs(1);
    cout << ans << '\n';
    return 0;
}

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