时间限制: 2 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
查看运行结果
题目描述 Description
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上。
输入描述 Input Description
给定棋盘的大小n (n ≤ 13)
输出描述 Output Description
输出整数表示有多少种放置方法。
样例输入 Sample Input
8
样例输出 Sample Output
92
数据范围及提示 Data Size & Hint
n<=13
(时限提高了,不用打表了)
1 #include<iostream>
2 #include<cmath>
3 using namespace std;
4 int tot;
5 int vis[1001];// 列
6 int zd[1001];//左方向对角线
7 int yd[1001];//右方向对角线
8 int n;
9 void f(int k)
10 {
11 if(k==n)
12 {
13 tot++;
14 return;
15 }
16 else
17 {
18 for(int j=1;j<=n;j++)
19 {
20 if(vis[j]==0&&zd[j+k]==0&&yd[k-j+n]==0)
21 {
22 vis[j]=1;
23 zd[j+k]=1;
24 yd[k-j+n]=1;
25 f(k+1);
26 vis[j]=0;
27 zd[j+k]=0;
28 yd[k-j+n]=0;
29 }
30 }
31 }
32 }
33 int main()
34 {
35
36 cin>>n;
37 f(0);// 一定是0,千万别是1 ,。。。。一位调试了1个小时的oier的忠告
38 cout<<tot;
39 return 0;
40 }