hdu2553 N皇后问题–DFS
最后更新于：2022-04-01 19:58:29
原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2553](http://acm.hdu.edu.cn/showproblem.php?pid=2553)
**一：原题内容**
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
~~~
1
8
5
0
~~~
Sample Output
~~~
1
92
10
~~~
**二：AC代码**
~~~
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1
#include
using namespace std;
int a[11][11];//皇后棋盘，第一行第一列舍弃，其中第一列用来存储每一行皇后的列坐标
int b[11];//打表所用的数组
int N;
int num;
void DFS(int n, int & m);
int main()
{
//////1.打表
for (int i = 1; i < 11; i++)
{
num = 0;
DFS(1,i);
b[i] = num;
}
//////2.
while (cin >> N&&N != 0)
{
cout << b[N] << endl;
}
return 0;
}
bool isLegal(int & x, int & y)//判断棋盘上坐标为x，y是否可以放置皇后
{
for (int i = 1; i < x; i++)
{
if (a[i][0] == y || abs(i - x) == abs(a[i][0] - y))
return false;
}
return true;
}
void DFS(int n,int & m)//n代表搜索到第n行，m代表是m皇后
{
if (n == m+1)
num++;
else
{
for (int i = 1; i <= m; i++)
{
if (isLegal(n, i))
{
a[n][0] = i;
//a[n][i]=1;
DFS(n + 1, m);
}
//a[n][i] = 0;
}
}
}
~~~
';