在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上，
你的任務是，對于給定的N，求出有多少種合法的放置方法，
Input
共有若干行，每行一個正整數N≤10，表示棋盤和皇后的數量；如果N=0，表示結束，
Output
共有若干行，每行一個正整數，表示對應輸入行的皇后的不同放置數量，
Sample Input
1 8 5 0Sample Output
1 92 10
思路：1.暴力法2.回溯法，找到皇后們處于同一列和斜線上時的條件
實作代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
int N,cot;
int size[11];
int ans[11];
void dfs(int n)
{
int flag;
if(n==N+1)
{
cot++;
return ;
}
for(int i=1;i<=N;i++)
{
size[n]=i;
flag=1;
for(int j=1;j<n;j++)
{
if(size[j]==i||((abs(n-j))==abs(size[j]-i)))
{
flag=0;
break;
}
}
if(flag) dfs(n+1);
}
}
int main()
{
for( N=1;N<=11;N++)
{
cot=0;
dfs(1);
ans[N]=cot;
}
while(scanf("%d",&N),N!=0)
{
printf("%d\n",ans[N]);
}
return 0;
}
注意：
1.為了避免時間超限，所以阿久提前打表了，
2.abs 函式是存在于多種編程語言（包括且不限于：C語言、C++、Fortran、Matlab、Pascal、Delphi、Visual Basic 和VBA）中的一種用于求資料絕對值的函式，頭檔案：stdlib.h，函式原型：int abs(int i);
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259313.html
標籤：其他
上一篇：基于C語言和LPC1114開發板的嵌入式實驗 SysTick實驗、定時器實驗、LED呼吸燈實驗、蜂鳴器實驗
下一篇：美味果凍