随笔-72  评论-126  文章-0  trackbacks-0
/*
ID:notonlysuccess
LANG:C++
TASK:checker
*/
#include
<stdio.h>
int cnt;
int ans[3][13];
int jilu[13];
int n,maxn;
void dfs(int row,int ld,int rd,int deep)
{
    
int i,buf,pos;
    
if(deep == n)
    {
        
if(cnt<3)
        {
            
for(i=0;i<n;i++)
                ans[cnt][i] 
= jilu[i];
        }
        cnt 
++;
        
return ;
    }
    buf 
= row | ld | rd;
    
for(i=0;i<n;i++)
    {
        pos 
= 1<<i;
        
if((buf & pos) == pos)
            
continue;
        jilu[deep] 
= i+1;
        dfs(row
+pos,(ld+pos)<<1,(rd+pos)>>1,deep+1);
    }
}
int main()
{
    freopen(
"checker.in","r",stdin);
    freopen(
"checker.out","w",stdout);
    
int i,j;
    scanf(
"%d",&n);
    cnt 
= 0;
    maxn 
= 1<<n;
    dfs(
0,0,0,0);
    
for(i=0;i<3 && i<cnt;i++)
    {
        
for(j=0;j<n-1;j++)
            printf(
"%d ",ans[i][j]);
        printf(
"%d\n",ans[i][j]);
    }
    printf(
"%d\n",cnt);
    
return 0;
}






哈哈,hdoj上超大数据量的N皇后也过了。。

#include<stdio.h>
int cnt;
int n,maxn;
void dfs(int row,int ld,int rd)
{
    
int buf,pos;
    
if(row == maxn)
    {
        cnt 
++;
        
return ;
    }
    buf 
= row | ld | rd;
    
for(pos = 1;pos <= maxn;pos <<= 1)
    {
        
if((buf & pos) == pos)
            
continue;
        dfs(row
+pos,(ld+pos)<<1,(rd+pos)>>1);
    }
}
int main()
{
    
int i,pos;
    
while(scanf("%d",&n),n)
    {
        cnt 
= 0;
        maxn 
= (1<<n) - 1;
        
for(i=0;i<n/2;i++)
        {
            pos 
= 1<<i;
            dfs(pos,pos
<<1,pos>>1);
        }
        cnt 
<<= 1;
        
if(n&1)
        {
            pos 
= 1<<i;
            dfs(pos,pos
<<1,pos>>1);
        }
        printf(
"%d\n",cnt);
    }
    
return 0;
}
posted on 2009-04-15 12:24 shǎ崽 阅读(1624) 评论(2)  编辑 收藏 引用

评论:
# re: 飘逸的N皇后问题位运算代码,纪念USACO创过第一关~~matrix67大牛博客上学的 2009-04-24 10:54 | Apple
按hint剪枝,比你的速度快~O(∩_∩)O~  回复  更多评论
  
# re: 飘逸的N皇后问题位运算代码,纪念USACO创过第一关~~matrix67大牛博客上学的 2009-04-28 14:41 | shǎ崽
@Apple
如何?
我usaco上是0.3s  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理