題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=2553

方法：?1.可以用對稱的思想，即：如果N是偶數，則只計算第一個皇后分別放在第一行的位置1到N/2這N/2個情況的結果和，最后再乘以2。如果是奇數，再單獨計算一個在N/2+1這個位置的結果。

　　　 2.一個皇后如果放在一個位置，要把該位置對應的行列上的位置和以該位置為起點，從左下 和 右下45讀的兩個方向延伸穿過的位置都設置為不可再放。

????????? 3.在狀態數中，在第i層為第i個皇后找位子其實就是在棋盤的第i行找。找不到就返回，否則修改棋盤，繼續收索，直到第N層也搜索成功，此時給結果加1.

感想：后期多看。

代碼：

View Code #include<iostream> #include<math.h> #include <algorithm> using namespace std; int n; int table[11]; struct Record {int row;int col; }; bool canPlace[11][11]; int total_sum=0; void usedPlace(int x,int y) {for(int i=x,j=y;i<=n&&j<=n;i++,j++)canPlace[i][j]=false;for(int i=x,j=y;i<=n &&j>=1;i++,j--)canPlace[i][j]=false;for(int i =x;i<=n;i++)canPlace[i][y]=false; }void DFSSearch( int start = 1) {if(start==n){total_sum++;return;}bool t_canPlace[11][11];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)t_canPlace[i][j] = canPlace[i][j];for(int i=1;i<=n;i++){if(canPlace[start+1][i]){usedPlace(start+1,i);DFSSearch(start+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)canPlace[i][j] = t_canPlace[i][j];}} } int main() {memset(table,-1,sizeof(table));while(scanf("%d",&n)&& n!=0){int sum=0;if(table[n]==-1){int boundary = n/2;total_sum=0;for(int i=1;i<=boundary;i++){memset(canPlace,true,sizeof(canPlace));usedPlace(1,i);DFSSearch();}sum+=total_sum*2;if(n%2!=0){total_sum=0;memset(canPlace,true,sizeof(canPlace));usedPlace(1,boundary+1);DFSSearch();sum+=total_sum;}table[n]=sum;}elsesum = table[n];cout<<sum<<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/kbyd/archive/2013/04/16/3024405.html

總結

以上是生活随笔為你收集整理的[HDU] 2553 N皇后问题-简单深搜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。