心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

lie[i]==false表示第i列还没有任何棋子;dui1[i]==false表示向右倾斜的、从上到下的第i条对角线上还没有任何棋子;dui2[i]==false表示向左倾斜的、从上到下的第i条对角线上还没有任何棋子。
利用这些记录优化搜索。
n==13的数据我用了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>3return;
        
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 阅读(330) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理