2508: 【普及/提高-】【P1219】八皇后 Checker Challenge

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：32 解决：9

题目描述

一个如下的 lns="http://www.w3.org/1998/Math/MathML">6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 lns="http://www.w3.org/1998/Math/MathML">2 4 6 1 3 5 来描述，第 lns="http://www.w3.org/1998/Math/MathML">� 个数字表示在第 lns="http://www.w3.org/1998/Math/MathML">� 行的相应位置有一个棋子，如下：

行号 lns="http://www.w3.org/1998/Math/MathML">1 2 3 4 5 6

列号 lns="http://www.w3.org/1998/Math/MathML">2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 lns="http://www.w3.org/1998/Math/MathML">3 个解。最后一行是解的总个数。

输入

一行一个正整数 lns="http://www.w3.org/1998/Math/MathML">�，表示棋盘是 lns="http://www.w3.org/1998/Math/MathML">�×� 大小的。

输出

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例输入 复制 

6

样例输出 复制 

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

提示

【数据范围】
对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，lns="http://www.w3.org/1998/Math/MathML">6≤�≤13。 

#include<bits/stdc++.h>
using namespace std;
#define maxn 100
int a[maxn], n, ans = 0;
int b1[maxn], b2[maxn], b3[maxn];
// 分别记录y,x+y,x-y+15是否被占用
void dfs(int x) { // 第x行的皇后放哪儿
    if (x > n) { // 如果所有皇后已经放置
        ans++; // 增加结果数量
        if (ans <= 3) { // 输出前三种答案
            for (int i = 1; i <= n; i++)
                printf("%d ", a[i]);
            puts("");
        }
        return;
    }
    for (int i = 1; i <= n; i++)
        if (b1[i] == 0 && b2[x + i] == 0 && b3[x - i + 15] == 0) {
            a[x] = i; // 记录放置位置
            b1[i] = 1; b2[x + i] = 1; b3[x - i + 15] = 1; // 占位
            dfs(x + 1); // 下一层递归
            b1[i] = 0; b2[x + i] = 0; b3[x - i + 15] = 0; // 取消占位
        }
}
int main(){
    scanf("%d",&n);
    dfs(1);
	printf("%d",ans); 
	return 0;
}

来源/分类

提交提交记录统计露一手!