洛谷P1219八皇后题解

洛谷P1219

题目传送门：https://www.luogu.com.cn/problem/P1219

题目简述：

输入n表示棋盘大小，n的范围是6<=n<=13

现在要按行顺序放置皇后，让皇后不互相攻击的情况下放置，也就是要安排列数，使得每一行每一列都有一个皇后

思路分析：

以n = 6为例子：

可以想象这道题的解答树，对于每一层有6个列数可以选择，然后每一个节点都有六个子节点，现在需要找出能走到要求深度的树的分支，输出前三个路径
比较显然的是会选择dfs来遍历树，但难点是每一次都要判断是否皇后之间有攻击

一开始的想法是弄一个vis表记录每一个禁着点，但是发现这太麻烦了，，
再思考一下其实是又数学关系的，一个是列数相等，一个是行差等于列差。

数据储存方式：
col[row]用这个储存列数，可以确定皇后的位置，row也就是dfs的深度

代码：

#include<cstdio>
#include<cstring>
#include<cmath>

int n;
int col[15];  //col[row] = 列
int cnt;

bool safe(int r, int c) {
	for (int i = 1; i < r; i++) {
		if (c == col[i])return 0;
		if (std::abs(c-col[i]) == r-i)return 0;
	}
	return 1;
}

void dfs(int row) {
	if (row == n + 1) {
		cnt++;
		if (cnt <= 3) {
			for (int i = 1; i <= n; i++) {
				printf("%d ", col[i]);
			}
			printf("\n");
		}
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (safe(row,i)) {
			col[row] = i;
			dfs(row + 1);
		}
	}
}

int main() {
	scanf("%d", &n);
	cnt = 0;
	dfs(1);
	printf("%d\n", cnt);
	return 0;
}

最后：