N皇后问题 HDU – 2553 深搜


原题

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

Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

Sample Input
1
8
5
0
Sample Output
1
92
10

代码

第一种解法(其实两种差不多)

#include <bits/stdc++.h>
using namespace std;
int n,k, p[9999999], hash_[9999999],sum;
void queen(int ordinal){
if (ordinal == n + 1){
sum++;
return;
}
else{
for (int x = 1; x <= n; x++){
bool flag = true;
if (!hash_[x]){
for (int pre = 1; pre < ordinal; pre++){
if (abs(ordinal - pre) == abs(x - p[pre])){
flag = false;
break;
}
}
if (flag){
hash_[x] = 1;
p[ordinal] = x;
queen(ordinal + 1);
hash_[x] = 0;
}
}
}
}
}

int main()
{
int a[10];
for(int i=0;i<10;i++){
sum=0;
n=i+1;
queen(1);
a[i]=sum;
}
while(cin>>k,k)
cout<<a[k-1]<<endl;
}

第二种解法

#include <bits/stdc++.h>
using namespace std;
int cnt,col[11],n; //cnt用来数当前 n*n 宫格所得的解的数目,col临时记录被占了的格子,n为输入的宫格边长
bool check(int column,int row){ //判断是否满足占格条件
for(int i=0;i<row;i++){ //遍历所有行,判断是否有打破规则的占格
if(col[i]==column||(abs(col[i]-column)==abs(i-row)))
//由于col是存放第 i 行被占用的列的下标,所以col[i]==column就表示这列已经被占了,不满足规定,需要重新选择列
//abs(col[i]-column)==abs(i-row)是判断是否在同一对角线的(两个列下标相减等于两个行下标相减),自行画图理解
return false;
}
return true;
}
void queen(int r){
if(r==n){ //如果达到最大行,获得一个解(因为如果某个解不可行是无法走到最大行的)
cnt++; //解的数目增加
return;
}
for(int column=0;column<n;column++){ //对列单独遍历
if(check(column,r)){ //判断当前坐标是否符合“与其他棋子不同行不同列”,“与其他棋子不同对角线”的规定
col[r]=column; //如果符合要求,那么就将当前行坐标对应的列坐标存入col里面(即存放棋子占用的格子的坐标)
queen(r+1); //由于当前行已选择了一列占格,此时需要看看下一行满足条件的列
}
}
}

int main(){
int save[10]; //存放十以内 n*n宫格的解的个数
for(int i=0;i<=10;i++){
cnt=0; //初始化
memset(col,0,sizeof(col)); //初始化col数组
n=i; //计算 1-10 的解数
queen(0); //深搜
save[i]=cnt;
}
while(cin>>n,n){
cout<<save[n]<<endl;
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

N皇后问题 HDU - 2553 深搜

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » N皇后问题 HDU – 2553 深搜
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏