首页 > 代码库 > n皇后问题

n皇后问题

2024-09-10 01:00:20   219人阅读

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

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     else17     {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 }

 

n皇后问题


联系
我们