hdu 2553:N皇后問題(DFS遍歴、水題)

N皇后問題
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6905    Accepted Submission(s): 3128
Problem Description
N*Nの四角い碁盤には、互いに攻撃しないようにN個の皇后が置かれている(すなわち、任意の2個の皇后は同じ列にいてはならず、同じ列にいても、碁盤の枠と45角の斜線にいてはならない.
あなたの任務は、与えられたNに対して、どれだけの合法的な配置方法があるかを求めることです.
 
 
Input
いくつかの行があり、行ごとに正の整数N≦10で、碁盤と皇后の数を表します.N=0の場合、終了を表します.
 
 
Output
いくつかの行があり、各行に正の整数があり、入力行に対応する皇后の異なる配置数を表します.
 
 
Sample Input
1
8
5
0
 
 
Sample Output
1
92
10
 
 
Author
cgf
 
 
Source
2008 HZNU Programming Contest
 
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1312  
1181  
2614  
1258  
1045  
 
DFS、水題.
すべての状況を再帰的に遍歴すればよい.コードは簡略化する必要がある.この問題に注意するには、事前に表を打つ必要がある.そうしないと、一度尋ねるたびにDFSを再確認し、提出がタイムアウトし、表を打つと1~10のすべての結果を記録し、質問するときに直接記録した結果を出力すればよい.
このように、このような結果がいくつかの値しかない場合、毎回再帰する必要はなく、すべての結果を直接表に出して最後に出力すればよい.そうしないと計算を繰り返すことになる.
 

 1 #include <iostream>

 2 using namespace std;  3 

 4 int n,sum;  5 int ans[12],sel[12];  6 

 7 int Abs(int n)  //    

 8 {  9     return n>0?n:-n; 10 } 11 

12 void f(int h) //   i      

13 { 14     if(h>n){    //  ，  +1

15         ++sum; 16         return ; 17  } 18     int i,x,y;    //（x，y）        

19     x = h;  //     

20     for(y=1;y<=n;y++){  //      21         //      ，           ，        

22         for(i=1;i<x;i++) 23             if(y==sel[i]) 24                 break; 25         if(i<x)     //  

26             continue; 27         //       

28         for(i=1;i<x;i++) 29             if(Abs(sel[i]-y)==x-i) 30                 break; 31         if(i<x)    //  

32             continue; 33 

34         sel[x] = y; //    ，          

35         f(h+1); 36  } 37 } 38 

39 int main() 40 { 41     for(n=1;n<=10;n++){ //  

42         sum = 0; 43         f(1); 44         ans[n] = sum; 45  } 46     while(cin>>n){ 47         if(n==0) break; 48         cout<<ans[n]<<endl; 49  } 50     return 0; 51 }

 
Freecode : www.cnblogs.com/yym2013