</pre>数据结构老师说,回溯法是程序设计的基本算法,八皇后这个问题不会就别学编程了了。本来真心对回溯法犯二,不过在刺激之下,,就搞了一搞,,不过还带看刘汝佳的书,,<img alt="哭" src="http://static.blog.csdn.net/xheditor/xheditor_emot/default/cry.gif" />真心挫爆了。。。<p></p><p>http://acm.hdu.edu.cn/showproblem.php?pid=2553,这是杭电这道题的链接 ,不过这个道题的时间有限制,,只靠回溯法会超时。。</p><pre name="code" class="cpp">#include <iostream>
using namespace std;
#define maxn 10000
int n,sum=0;
int a[maxn];
void find(int cur)
{
int i,j;
if(cur==n)
{
sum++;
}
else
for(i=0; i<n; i++)
{
int ok = 1;
a[cur]=i;
for(j=0; j<cur ; j++)//判断之前的
if(a[cur]==a[j]||j-a[j]==cur-a[cur]||a[cur]+cur==a[j]+j)//判断是否满足条件,因为是按行放的,所以无需考虑行数,只要考虑列和对角线就ok了。
//至于为什么这样判断,只要画个图找出行和列的关系就行了。 { ok=0; break; } if(ok) find(cur+1); } } int main() { while(cin>>n) { if(n==0)break; sum=0; find(0); cout << sum << endl; } return 0; }
以我的智商,,能过的也就打表了
#include<iostream> #include<cstdio> #include<cstdlib> const int MAX=11; int Queen[MAX]={0,1,0,0,2,10,4,40,92,352,724}; using namespace std; int main() { int n; while(cin>>n,n) { cout<<Queen[n]<<endl; } return 0; }
在这里贴一个能过的代码用的是搜索,,不过充分体现了位运算的速度之快。(参考某位大神的代码,怎么回事我也不明白。。。)
#include<cstdio> #include<cstring> using namespace std; int N,High,ans; void DFS(int row,int ld,int rd) { if(row == High){ ans++; return;} int Pos = ((~(row | ld | rd)) & High); while(Pos) { int P = Pos & (-Pos); Pos = Pos - P; DFS(row+P, (ld+P)<<1, (rd+P)>>1); } } int main() { while(~scanf("%d",&N) && N) { High = (1<<N)-1; ans = 0; DFS(0,0,0); printf("%d\n",ans); } return 0; }