HDU 2553 N皇后问题

//这道题首先想到的是枚举，但时间复杂度高。然后我用的回溯法，就是逐个尝试，如果合适就继续，否则就回溯到上一行继续 //最开始的代码，我开始一直用c++交的，但count变量有问题（我也不知道为啥，知道的可以评论下），然后我就改用G++交结果TTE（超时） #include<iostream> #include<math.h> using namespace std; int N,count; int queenpos[10]; int Nqueen(int k); int main() { while(cin>>N) { count=0; if(N==0) break; cout<<Nqueen(0)<<endl; } return 0; } int Nqueen(int k) { if(k==N)//当0~k-1行都摆好，统计+1 { count++; } int i,j; for(i=0;i<N;i++)//在第k行逐个尝试0~N-1列 { for(j=0;j<k;j++) { if(queenpos[j]==i||abs(queenpos[j]-i)==abs(k-j))//与0~k-1行有冲突（在同一列或者同一斜线） break; } if(j==k)//如果j==k，说明上面并没有break，此位置可行 { queenpos[j]=i;//记录第k行的棋子位置 Nqueen(k+1);//递归调用 } } return count; } //百度之后才知道，因为数据量比较大，需要预处理 #include<iostream> #include<math.h> using namespace std; int n,count=0; int queenpos[10]; int main() { void Nqueen(int ); int a[11]; for(int i=1;i<=10;i++)//预处理 { n=i; count=0; Nqueen(0); a[n]=count;//提前将结果存到数组里 } while(cin>>n) { if(n==0) break; cout<<a[n]<<endl; } return 0; } void Nqueen(int k) { int i,j; if(k==n) count++; for(i=0;i<n;i++)//在第k行逐个尝试0~N-1列 { for(j=0;j<k;j++) { if(queenpos[j]==i||abs(queenpos[j]-i)==abs(k-j)) break; } if(j==k) { queenpos[j]=i; Nqueen(k+1); } } }