1295 N皇后问题

题目描述  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

（时限提高了，不用打表了）

分类标签 Tags 点此展开 

 

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; int tot=0,q; int a[100]={0};bool b[100]={0},c[100]={0},d[100]={0}; void dfs(int n) { for(int i=1;i<=q;i++) { if ((!b[i])&&(!c[n+i])&&(!d[n-i+q-1])) { a[n]=i; b[i]=1; c[n+i]=1; d[n-i+q-1]=1; if(n==q)tot++; else dfs(n+1); b[i]=0; c[n+i]=0; d[n-i+q-1]=0; } } } int main() { cin>>q; dfs(1); cout<<tot; return 0; }

 

转载于:https://www.cnblogs.com/sssy/p/6603623.html