/*
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ǎ崽 閱讀(1717)
評論(2) 編輯 收藏 引用