C/C++教程

ACM-ICPC寒假算法训练1：搜索专题 黑白皇后问题（进一步思考深度遍历）

本文主要是介绍ACM-ICPC寒假算法训练1：搜索专题 黑白皇后问题（进一步思考深度遍历），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
2*n皇后问题 
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

const int maxn = 10;
int n, ans, mp[maxn][maxn];
int col_black[maxn], diag1_black[2 * maxn], diag2_black[2 * maxn];
int col_white[maxn], diag1_white[2 * maxn], diag2_white[2 * maxn];
void dfs(int k) {
	if (n + 1 == k) {
		ans++;
		return;
	}
	for (int black = 1; black <= n; black++) {
		for (int white = 1; white <= n; white++) {
			if (col_black[black] || col_white[white])	continue;
			if (black == white || !mp[k][black] || !mp[k][white])	continue;
			if (diag1_black[k + black - 1] || diag2_black[k - black + n])	continue;
			if (diag1_white[k + white - 1] || diag2_white[k - white + n])	continue;
			col_black[black] = diag1_black[k + black - 1] = diag2_black[k - black + n] = 1; mp[k][black] = 0;
			col_white[white] = diag1_white[k + white - 1] = diag2_white[k - white + n] = 1; mp[k][white] = 0;
			dfs(k + 1);
			col_black[black] = diag1_black[k + black - 1] = diag2_black[k - black + n] = 0; mp[k][black] = 1;
			col_white[white] = diag1_white[k + white - 1] = diag2_white[k - white + n] = 0; mp[k][white] = 1;
		}
	}
}


int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &mp[i][j]);
	dfs(1);
	printf("%d", ans);
	return 0;
}```
这篇关于ACM-ICPC寒假算法训练1：搜索专题 黑白皇后问题（进一步思考深度遍历）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航