HDU 2553 N皇后问题 （回溯DFS）

HDU 2553 N皇后问题 （回溯DFS）

N皇后问题

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

Problem Description

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

Input

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

Output

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

Sample Input

1850

Sample Output

19210

Author

cgf

Source

​​2008 HZNU Programming Contest ​​

Recommend

lcy   |   We have carefully selected several similar problems for

you:  ​​2614​​​ ​​1258​​​ ​​1045​​​ ​​1426​​​ ​​1035​​

题解：打表（1~10）+回溯dfs。。。。

AC代码：

#include#include#include#includeusing namespace std;int x[15],num[15]={0};int sum;int n;int check (int k){ for(int i=1;in) { sum++; } else for(int i=1;i<=n;i++) { x[a]=i; //第 a个皇后放的列数 i if(check(a)) { dfs(a+1); } }}int main(){ int N; for(int i=0;i<=10;i++) { n=i; //表示几个皇后 sum=0; //每次都置零 dfs(1); //每次从第一个皇后开始 num[i]=sum; //存储方案 } while(~scanf("%d",&N)&&N) { printf("%d\n",num[N]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。