【HDU】2553 - N皇后问题（dfs）

FishWang

发布于 2025-08-27 09:28:11

14100

代码可运行

运行总次数：0

代码可运行

点击打开题目

N皇后问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18337 Accepted Submission(s): 8295

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

Sample Output

   1
92
10

Author

cgf

Source

2008 HZNU Programming Contest

要先dfs打表啊，输入后再进行dfs的话会超时的！

话说：如果数很大的话，就算先打表也会超时，完全可以打个表，然后手写一个表，就是在常数复杂度下出结果了。（好无耻的方法=。=）

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
bool vis[3][44];		//0为列，1为主对角线，2为副对角线 
int n;
int ans[14];
void dfs(int x,int y,int ant)
{
	if (x > n)
		return;
	if (ant > x)
		return;
	if (ant == n)
	{
		ans[n]++;
		return;
	}
	for (int i = 1 ; i <= n ; i++)
	{
		if (vis[0][i] || vis[2][x+1+i] || vis[1][i-x-1+10])
			continue;
		vis[0][i] = vis[2][x+1+i] = vis[1][i-x-1+10] = true;
		dfs(x+1 , i , ant+1);
		vis[0][i] = vis[2][x+1+i] = vis[1][i-x-1+10] = false;
	}
}
int main()
{
	CLR(vis,false);
	for (n = 1 ; n <= 10 ; n++)
	{
		ans[n] = 0;
		for (int i = 1 ; i <= n ; i++)
		{
			vis[0][i] = vis[2][1+i] = vis[1][i-1+10] = true;
			dfs(1,i,1);
			vis[0][i] = vis[2][1+i] = vis[1][i-1+10] = false;
		}
	}
	while (~scanf ("%d",&n) && n)
		printf ("%d\n",ans[n]);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

return