百练oj 2754 八皇后 dfs

缘起

【1】中早就写过八皇后. 但是没有提交过. 这么经典的题目怎么能不提交呢? 遂找到 百练oj 2754 八皇后

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
总时间限制: 1000ms 内存限制: 65536kB

描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上
（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇
后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

样例输入
2
1
92

样例输出
15863724
84136275

很简单, 求出92个字典序升序的解存数组即可. 题目规定的皇后串是第i行皇后的列数. 所以我们在dfs的时候应该逐行放置皇后. 而且字典序升序的关键就是按照 1~8的顺序开拓放置皇后的列数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#define ABS(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))

int ans[100], a[10], top;
bool v[10];

int hunter() // 洪特规则
{
	int q = 0;
	for (int i = 1; i<=8; i++)
	{
		q = q*10+a[i];
	}
	return q;
}

bool ok(int row, int col) // row行col列放置皇后可以吗? 注意, 因为v[i]的检查, 所以不用担心行或者列会重复(因为行是逐行放置过来的,而列在进入此方法之前已经用v[i]判断过),所以只需要检查斜对角
{
	for (int i = 1; i<row; i++) // 检查之前的放置
	{
		if (ABS(row, i)==ABS(col, a[i])) // 只在不在斜对角
		{
			return false;
		}
	}
	return true;
}

void dfs(int row) // row表示现在决定的是第row行的皇后的摆放列数
{
	if (row==9) // 已经得到了一组解
	{
		ans[top++] = hunter();
		return;
	}
	for (int i = 1; i<=8; i++) // 从第一列开始考察能不能放置皇后
	{
		if (v[i]) // 这一列已经被占用了
		{
			continue;
		}
		if (ok(row, i)) // 如果row行的皇后放置在i列可以的话
		{
			a[row] = i;
			v[i] = true;
			dfs(row+1);
			v[i] = false; // 改回来
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	dfs(1);
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		int x;
		scanf("%d", &x);
		printf("%d\n", ans[--x]);
	}
	return 0;
}

ac情况

影法师 Accepted 136kB 1ms 1376 B G++ 刚刚

参考

【1】https://yfsyfs.github.io/2019/05/19/%E5%85%AB%E7%9A%87%E5%90%8E/