首页技术正文

COJ 0024 N皇后问题

开发者艺涵技术 2022年11月17日

0 收藏 824 点赞 4,601 浏览 1070 个字

N皇后问题

难度级别：B；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

在N*N的方格棋盘放置N个皇，使得它们不相互攻击（即任意2个皇后不允许处在同一行，或同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种符合要求放置方法。

输入

输入中有一个正整数N≤20，表示棋盘和皇后的数量

输出

为一个正整数，表示N个皇后的不同放置方法数。

输入示例

输出示例

题解：上来写了一发常数巨大= =，别用二维数组= =

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=;
 int ans=,a[maxn],n;
 bool check(int t){
     for(int i=;i<t;i++) if(a[t]==a[i]||t+a[t]==i+a[i]||t-a[t]==i-a[i]) return false;
     return true;
 }
 void dfs(int d){
     if(d==n){ans++;return;}
     for(int i=;i<n;i++){
         a[d]=i;if(check(d)) dfs(d+);
     } return;
 }
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
     while(isdigit(ch))x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
     int len=,buf[];while(x)buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
 }
 void init(){
     n=read();
     dfs();write(ans);
     return;
 }
 void work(){
     return;
 }
 void print(){
     return;
 }
 int main(){init();work();print();return ;}