HDU N皇后问题 2553 【深搜练习】

悠悠 2022-06-05 09:46 170阅读 0赞

## N皇后问题 ##

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 27121 Accepted Submission(s): 12073

#### 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

#### 题意概括： ####

在n\*n的棋盘上放n个皇后，任意两个皇后不能处在同一行或同一列或处在对角线上。

#### 解题分析： ####

需要把十种情况打表，不然会超时。

#### AC代码： ####

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    
    #define N 12
    
    int e[N][N], a[N], List[N], n, ans;
    
    bool f(int x, int y)
    {
        int i, j;
        for(i = 1; i < x; i++){
            for(j = 1; j <= n; j++)
                if(e[i][j] && fabs(i-x) == fabs(j-y))//判断对角线上是否有皇后
                    return false;
        }
        return true;
    }
    
    void dfs(int t)
    {
        if(t > n){
            ans++;
            return ;
        }
        for(int i = 1; i <= n; i++){
            if(!e[t][i] && !List[i] && f(t, i)){
                e[t][i] = List[i] = 1;
                dfs(t+1);
                e[t][i] = List[i] = 0;
            }
        }
    }
    
    void solve(void)
    {
        for(int i = 1; i <= 10; i++){
            memset(e, 0, sizeof(e));
            memset(List, 0, sizeof(List));
            ans = 0;
            n = i;
            dfs(1);
            a[i] = ans;
        }
    }
    
    int main()
    {
        int m;
        solve();//将十种情况打表，不然会超时
        while(scanf("%d", &m), m)
            printf("%d\n", a[m]);
        return 0;
    }