题意：N皇后
方法：BFS+打表
View Code
1 #include<stdio.h> 2 #include<string.h> 3 const int maxn = 21; 4 int sd[ maxn*2 ],c[ maxn ],md[ maxn*2 ]; 5 struct node{ 6 int r,c,flag; 7 }p,stack[ maxn*maxn ]; 8 int ans,n; 9 10 void bfs(){ 11 int top=-1; 12 for( int i=n-1;i>=0;i-- ){ 13 stack[ ++top ].r=0; 14 stack[ top ].c=i; 15 stack[ top ].flag=0;//0 stand for not the path 16 } 17 memset( sd,0,sizeof(sd)); 18 memset( c,0,sizeof(c)); 19 memset( md,0,sizeof(md)); 20 while( top>=0 ){ 21 node now; 22 now=stack[ top ]; 23 if( now.flag==0 ){ 24 if( sd[ now.r+now.c ]==1 || c[ now.c ]==1 || md[ now.r-now.c+n-1 ]==1 ) top--; 25 else { 26 sd[ now.r+now.c ]=c[ now.c ]=md[ now.r-now.c+n-1 ]=1; 27 stack[ top ].flag=1;//标记待会要出栈 28 if( now.r==n-1 ) ans++; 29 else{ 30 for( int i=n-1;i>=0;i--){ 31 stack[++top].r=now.r+1; 32 stack[top].c=i; 33 stack[top].flag=0; 34 }//put the next line into the stack 35 } 36 } 37 } 38 else{ 39 sd[ now.r+now.c ]=c[ now.c ]=md[ now.r-now.c+n-1 ]=0; 40 top--; 41 } 42 } 43 return ; 44 } 45 46 int main(){ 47 while( scanf("%d",&n) && n ){ 48 ans=0; 49 bfs(); 50 printf("%d\n",ans); 51 } 52 return 0; 53 }