本文主要是介绍hdu2553八皇后问题(DFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
1 8 5 0
1 92 10DFS搜索题
打表防止超时!
代码
#include<iostream>
using namespace std;
long long ans[12]; //打表存储答案
long long cnt;
int vis[12][12]; //这个就是棋盘了,等于0就是没放棋子,等于1就是放了
bool check(int r,int c) //判断能不能放
{for(int i=1;i<r;i++) //因为是一行一行递归过来的,所以只要检查这一列有没有if(vis[i][c])return false;for(int i=c,j=r;i<=10&&j>=1;i++,j--) //对角线if(vis[j][i])return false;for(int i=c,j=r;i>=1&&j>=1;i--,j--) //对角线if(vis[j][i])return false;return true;
}
void trial(int i,int n) //表示此时已经在前i-1行放了棋子了,总共有n*n的棋盘
{if(i>n) //说明已经放了n个棋子了cnt++;else //咱接着放for(int j=1;j<=n;j++)if(check(i,j)){vis[i][j]=1; //放下去就标记trial(i+1,n);vis[i][j]=0; //拿起来就取消标记,还原现场}
}
void f() //开开心心算完结果
{for(int i=1;i<11;i++){cnt=0;trial(1,i);ans[i]=cnt;}
}
int main()
{int N;f();while(cin>>N&&N){cout<<ans[N]<<endl;}return 0;
}
/* 1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
*/
这篇关于hdu2553八皇后问题(DFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!