NO IMAGE

題目:

在N*N的方格棋盤放置了N個皇后,使得它們不相互攻擊(即任意2個皇后不允許處在同一排,同一列,也不允許處在與棋盤邊框成45角的斜線上。 
你的任務是,對於給定的N,求出有多少種合法的放置方法。

Input

共有若干行,每行一個正整數N≤10,表示棋盤和皇后的數量;如果N=0,表示結束。

Output

共有若干行,每行一個正整數,表示對應輸入行的皇后的不同放置數量。

Sample Input

1
8
5
0

Sample Output

1
92
10

解題思路:

    DFS逐層考慮就行了,但是這道題做的時候一直超時,,,,後來才知道可以通過預處理節省時間,,,,預處理尤其對於一些輸入範圍比較小的題目有效,可以在輸入之前把所有可能的情況考慮到並計算出結果,輸入時直接調之前的結果就行了,這種技巧在複雜題目中也可以用,如果時間要求比較高,老是超時的話,可以考慮將某一部分重複計算的內容提前算好儲存在陣列中,直接呼叫就行了。

程式碼:

#include <iostream>
#include <map>
#include <cmath> 
#include <cstdio>
#include <cstring> 

using namespace std;

int n;
int ans=0;
int ma[11];

int ab(int a){
    if(a<0)return -a;
    else return a;
}

bool check(int x,int y){
    bool an=true;
    for(int i=1;i<=n;i ){
        if(ma[i]==0)break;
        if(i==x||ma[i]==y||ab(i-x)==ab(ma[i]-y)){
            an=false;
            break;
        }        
    }
    return an;
}

void dfs(int x){
    if(x>n)ans ;
    else{
        for(int i=1;i<=n;i ){ 
            ma[x]=0;
            if(check(x,i)){                
                ma[x]=i;                
                dfs(x 1);    
            }
        }
    }
}

int main(){
    int a;
    ma[1]=0;
    int an[11];
    for(int i=1;i<=10;i ){
        n=i;
        dfs(1);
        an[i]=ans;
        ans=0;
    }
    while((a=scanf(“%d”,&n))){
        if(n==0)break;
        printf(“%d\n”,an[n]);
    }
    cout<<“error,a=”<<a<<endl;
    system(“pause”); 
    return 0;
}