18124?N皇后問題
時間限制:2000MS? 內存限制:65535K
提交次數:0 通過次數:0
題型: 編程題???語言: G++;GCC;VC
?
Description
有N*N的國際象棋棋盤，要求在上面放N個皇后，要求任意兩個皇后不會互殺，有多少種不同的放法？
輸入格式
每一個數為T，代表CASE的數量，T<=13 此后，每行一個數N（13>=N>0）
輸出格式
每一個CASE，輸出對應答案
?
輸入樣例
2 4 5
?
輸出樣例
2 10
?
作者
?admin
SCAU-N皇后問題—回溯。輸入n,求出在n*n的棋盤上放置n個皇后可以有多少種解；就是一個八皇后問題，而且題目的n也非常的小，時間還給了2000ms，就算暴力回溯O(n^2)的復雜度都可以過。但這里介紹一個優化上的技巧。 ? ?皇后可以攻擊到同行同列和兩條對角線上的棋子，，那么肯定是一行行的放置，一行和一列都是只能放置一個棋子的。 ?在判斷同列的時候，開一個row[MAXN+5]的數組來標記哪些列放置了皇后。 ?對于兩個對角線；要判斷是否已放有棋子，就只要再開個二維的數組diagonal[2][MAXN*2+5]; ? 其中，y-x是主對角線，y+x是副對角線。 但y-x可能為負數，所以要寫成y-x+n; 在判斷到當前cur行上的位置j可以放置的話，就把diagonal[0][cur-j+n]和diagonal[1][cur+j]都標記為1 以此表示該條對角線上已經放置有棋子了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <utility> 13 #include <vector> 14 #define ll long long 15 #define inf 0x3f3f3f3f 16 using namespace std; 17 18 int row[20],diagonal[2][30];//標記列和兩條對角線的數組 19 int cnt,n; 20 void dfs(int cur) 21 { 22 if(cur==n+1) //到達遞歸邊界 23 { 24 cnt++; 25 return; 26 } 27 for(int i=1;i<=n;i++) 28 { //判斷列上、兩條對角線上是否已有棋子 29 if(!row[i]&&!diagonal[0][cur+i]&&!diagonal[1][cur-i+n]) 30 { 31 row[i]=diagonal[0][cur+i]=diagonal[1][cur-i+n]=1; 32 dfs(cur+1); 33 row[i]=diagonal[0][cur+i]=diagonal[1][cur-i+n]=0; 34 } 35 } 36 } 37 int main() 38 { 39 //freopen("input.txt","r",stdin); 40 memset(row,0,sizeof(row)); 41 memset(diagonal,0,sizeof(diagonal)); 42 int t; 43 scanf("%d",&t); 44 while(t--) 45 { 46 scanf("%d",&n); 47 cnt=0; 48 dfs(1); 49 printf("%d\n",cnt); 50 } 51 return 0; 52 }
?
方式)
