首页 > 代码库 > HDU - 2553 N皇后问题（dfs）

HDU - 2553 N皇后问题（dfs）

2024-09-12 12:58:27   218人阅读

题意：每行放一个棋子，棋子不能在同一行同一列，对角线。

这道题关键在剪枝。剪枝完了就是递归咯。

剪枝：

(a[i]数组里面装选择的列).

某一行的a[i]不能和a[n]冲突，所以有以下4个需要判断的条件:

a.行与行之间不能冲突，但是因为我们就是每一行求一个皇后位置，所以肯定不会冲突，不需要考虑啦。

b.列与列直接不能冲突，a[n]!=a[i]。

c.不在同一对左角线，a[n]-a[i]!=n-i。

d.不在同一对右角线，a[n]-a[i]!=-(n-i)。

然后c和d合并一下就是abs(a[n]-a[i])!=abs(n-i)。

(-?-;)做了好久，一直时间超限。然后看到网上说先打个表，然后就AC了。。。

 1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4  5 int a[11],solve[11]; 6 int cnt,n; 7  8 int check(int a[],int m){ 9     for(int i=1;i<m;i++){10         if(abs(a[i]-a[m])==abs(i-m)||a[i]==a[m])//判断条件,不在同一列和斜对角. 11         return 0;12     }13     return 1;14 }15 16 void dfs(int index){17     for(int j=1;j<=n;j++){18         a[index]=j;19         if(check(a,index)){20             if(index<n) dfs(index+1);21             else if(index==n) cnt++;22         }23     }24 } 25 26 int main(){27     for(int i=1;i<=10;i++){28         n=i;29         cnt=0;30         dfs(1);31         solve[i]=cnt;32     }33     int o;34     while(cin>>o&&o!=0){35         cout<<solve[o]<<endl;36     }37     return 0;38 }

 

HDU - 2553 N皇后问题（dfs）


联系
我们