【HDU2553】N皇后问题

N皇后问题

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

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

Sample Output

1
92
10

题解：N皇后是经典的深搜题目但是这道题直接深搜的话会TLE 我的想法是既然每一列每一行一定会有一个皇后那么深搜就记录每一列的皇后在哪一行之后通过一个check函数判断皇后是否在当前行或者当前列或者斜线方向有冲突
最后如果都没有冲突且每一列都已经有了皇后则就是可以的放置方案 ++ans 最后搜索出所有的结果
但是实际上这种方法虽然优化了还是会TLE 下面我先拿出来TLE的代码

#include <cstdio>
#include <cstring>

int ans, n;
int an[11];

bool check(int k);
void dfs(int k);

int main(){
    while(scanf("%d", &n) != EOF && n){
        memset(an, 0, sizeof(an));
        ans = 0;
        dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}

bool check(int k){
    for(int i = 1; i < k; ++i){
        if(an[k] == an[i] || an[k]-an[i] == k-i || an[k]-an[i] == i-k){
            return false;
        }
    }

    return true;
}

void dfs(int k){
    if(k == n+1){
        ++ans;
        return ;
    }

    for(int i = 1; i <= n; ++i){
        an[k] = i;
        if(check(k)){
            dfs(k+1);
        }
    }
}

于是我又加了一个小的优化先把所有的方案数求出来用一个数组存放再根据输入从数组中选取相应值输出
下面是AC代码

#include <cstdio>
#include <cstring>

int sum, n;                 //n作为输入
int ans[11], an[11];        //ans存放方案数  an存放相应列的皇后所在行

bool check(int k);          //校验函数
void dfs(int k);            //深搜函数

int main(){
    for(int i = 1; i < 11; ++i) {           //先将相应的方案数算出
		n = i;
		memset(an, 0, sizeof(an));          
		sum = 0;                            //每一次都要赋初值
		dfs(1);
		ans[i] = sum;                       //存放对应方案数
	}
    while(scanf("%d", &n) != EOF && n){
        printf("%d\n", ans[n]);             
    }
    return 0;
}

bool check(int k){
    for(int i = 1; i < k; ++i){             
        if(an[k] == an[i] || an[k]-an[i] == k-i || an[k]-an[i] == i-k){
            return false;
        }
    }

    return true;
}

void dfs(int k){
    if(k == n+1){
        ++sum;
        return ;
    }

    for(int i = 1; i <= n; ++i){
        an[k] = i;
        if(check(k)){
            dfs(k+1);
        }
    }
}

【HDU2553】N皇后有关问题

N皇后问题

相关推荐