搜索：N皇后

N皇后问题是DFS的代表性问题，其最难的地方就是在判重这里，想明白了怎么判重的话问题就很显然了。

这里给出两份代码，其中第一份代码的效率更好，就是在判重上下了功夫。当然，我记得还有使用位运算进行判重的方法，这里就先不介绍了。

首先是第一份代码，二维数组直接进行判重。

 #include<iostream>

 using namespace std;

 int n,ans=;

 int a[],v[][];

 void dfs(int dp)

 {

     if(dp>n)

     {

         ans++;

         return;

     }

     for(int i=;i<n;i++)

     if(!v[][i]&&!v[][dp+i]&&!v[][dp-i+n])

     {

         v[][i]=v[][dp+i]=v[][dp-i+n]=;

         dfs(dp+);

         v[][i]=v[][dp+i]=v[][dp-i+n]=;

     }

 }

 int main()

 {

     cin>>n;

     dfs();

     cout<<ans;

     return ;

 }

第二份代码的判重思路还是很容易看懂的，只不过效率不如第一份代码的好。

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int n;

 int ans=;

 int c[maxn];

 bool check(int x)

 {

     for(int i=;i<x;i++)

     {

         if(c[x]==c[i]||x-c[x]==i-c[i]||x+c[x]==i+c[i])

             return false;

     }

     return true;

 }

 void dfs(int dp)

 {

     if(dp>n)

     {

         ans++;

         return;

     }

     for(int i=;i<=n;i++)

     {

         c[dp]=i;

         if(check(dp))

             dfs(dp+);

         c[dp]=;

     }

 }

 int main()

 {

     cin>>n;

     dfs();

     cout<<ans<<endl;

     return ;

 }

巴特西

搜索：N皇后

最新文章

热门文章