C语言DFS(6)___八皇后问题(Hdu 2612)
你的任务是,对于给定的N,求出有多少种合法的放置方法。
1 8 5 0
1 92 10
#include <stdio.h> #include <iostream> using namespace std; int map[20],a[20],hang[20],n,cnt; void DFS(int num) { int i,j,flag; if(num==n+1)//到n也成立了才会搜索n+1 { cnt++;return; } for(i=1;i<=n;i++) if(!hang[i])//不在同一行 { flag=1;map[num]=i;//第num列第i行放第num个皇后 for(j=1;j<num;j++) if((map[num]-num==map[j]-j)||(map[num]+num==map[j]+j))//判断是否在对角线上 { flag=0;break; } if(flag) { hang[i]=1; DFS(num+1);//递归调用 hang[i]=0; } } } int main() { int i,m; for(i=1;i<11;i++)//打表列出N个皇后对应几种方法 { memset(map,0,sizeof(map)); memset(hang,0,sizeof(hang)); n=i;cnt=0; DFS(1); a[i]=cnt; } while(cin>>m&&m!=0) cout<<a[m]<<endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。