首页 > > 程序设计 > C/C++ >

n皇后问题

2018-06-17 23:00:54来源：未知阅读 ()

1295 N皇后问题

时间限制: 2 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。

输入描述 Input Description

给定棋盘的大小n (n ≤ 13)

输出描述 Output Description

输出整数表示有多少种放置方法。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 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 }