lie[i]==false表示第i列還沒有任何棋子；dui1[i]==false表示向右傾斜的、從上到下的第i條對(duì)角線上還沒有任何棋子；dui2[i]==false表示向左傾斜的、從上到下的第i條對(duì)角線上還沒有任何棋子。
利用這些記錄優(yōu)化搜索。
n==13的數(shù)據(jù)我用了403ms。
以下是我的代碼：
#include<iostream>
#include<string.h>
#define maxn 17
using namespace std;
long n,cnt,ans[maxn];
bool lie[maxn],dui1[2*maxn],dui2[2*maxn];
long f1(long x,long y)
{
return (x-y+n);
}
long f2(long x,long y)
{
return (x+y-1);
}
void dfs(long dep)
{
if(dep>n)
{
cnt++;
if(cnt>3) return;
for(long i=1;i<=n;i++)
{
if(i!=1) cout<<" ";
cout<<ans[i];
}
cout<<endl;
return;
}
for(long i=1;i<=n;i++)
if(!lie[i]&&!dui1[f1(dep,i)]&&!dui2[f2(dep,i)])
{
lie[i]=dui1[f1(dep,i)]=dui2[f2(dep,i)]=true;
ans[dep]=i;
dfs(dep+1);
lie[i]=dui1[f1(dep,i)]=dui2[f2(dep,i)]=false;
}
}
int main()
{
cin>>n;
cnt=0;
memset(lie,false,sizeof(lie));
memset(dui1,false,sizeof(dui1));
memset(dui2,false,sizeof(dui2));
dfs(1);
cout<<cnt<<endl;
return 0;
}
posted on 2010-10-22 21:35
lee1r 閱讀(349)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索