N皇后问题的两种算法速度比较

C语言 码拜 9年前 (2015-05-11) 1116次浏览 0个评论

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

对于这个经典的问题,通常有一下两种算法。我看一本算法书上说第二种效率要比第一种高,为啥第一种算法可以AC而第二个却超时了?请教各位大神!

算法一:

#include<iostream>
using namespace std;
int n,c[15],cnt,ans[15];
void DFS(int cur)
{
     if( cur==n){
         cnt++;
         return ;
     }
     else{
          for(int i=0; i<n; i++){
               c[cur]=i;
               bool flag=true;
               for(int j=0; j<cur; j++){
                    if( c[j]==i|| c[j]-j==i-cur|| c[j]+j==cur+i){
                        flag=false;
                        break;
                    }
               }
               if( flag)
                   DFS(cur+1);
          }
     }          
}
int main()
{
    int i;
    for( i=1; i<11; i++){
         memset(c,0,sizeof(c));
         cnt=0;
         n=i;
         DFS(0);
         ans[i]=cnt;
    }
    while( scanf("%d",&n)&&n){
           printf("%d\n",ans[n]);
    }
}

算法二:

#include <stdio.h>
int tot=0;
int n;
int c[100];
void search(int cur);
int main()
{
    while(~scanf("%d",&n))
    {
        search(0);
        printf("%d\n",tot);
    }
    return 0;
}
void search(int cur)
{
    int i,j,ok;//ok的值定在第i列,即判断第i列是否可以放皇后
    if(cur==n)tot++;
    else for(i=0;i<n;i++){//判断第cur行的第i列是否可以存放元素
        c[cur]=i;
        ok=1;
        for(j=0;j<cur;j++){
            if(c[cur]==c[j]||c[j]+j==c[cur]+cur||j-c[j]==cur-c[cur])
            {ok=0;break;}
            if(ok)search(cur+1);
        }
    }
}
40分
参考代码
https://github.com/707wk/Practice-Code-For-CPP/blob/master/20150326001.c

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明N皇后问题的两种算法速度比较
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!