P1219 N皇后
2024-09-04 17:59:38
P1219 N皇后
题目描述
检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
输入输出格式
输入格式:
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式:
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
输入输出样例
输入样例
6
输出样例
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明
题目翻译来自NOCOW。
USACO Training Section 1.5
代码:
#include"bits/stdc++.h"
#define pi(x) printf("%d\n",x)
using namespace std;
int n,ans;
int s[];
bool ck(int k)
{
for(int i=;i<k;i++){
if(s[i]==s[k]||(abs(i-k)==abs(s[i]-s[k]))) return ;//列与对角线
}
return ;
} void dfs(int id)
{
if(id==n+)
{
ans++;
if(ans<=)
for(int i=;i<=n;i++) printf("%d%c",s[i],i==n?'\n':' ');
return;
}
for(int i=;i<=n;i++){
s[id]=i;
if(ck(id)==) dfs(id+);
s[id]=;
}
}
int main ()
{
ios::sync_with_stdio();
memset(s,, sizeof(s));
ans=;
cin>>n;
dfs();
pi(ans);
return ;
}
最新文章
- RHEL5.8配置NFS服务
- 在VS中MFC、ATL与WIN32有什么联系或区别?
- Qt 自定义 滚动条 样式(模仿QQ)
- ios开发入门篇(二):Objective-C的简单语法介绍
- SQL:deferrable initially deferred
- 新浪授权认证(不用SDK)
- sublime快捷键收藏
- 第二章排错的工具:调试器Windbg(上)
- java学习笔记 --- 多态
- An internal error occurred during: ";Launching New_configuration";
- 浏览器输入URL到响应页面的全过程
- 【Unity3D与23种设计模式】外观模式(Facade)
- (二十五)键盘的设置与TextField细节处理
- DBUtils工具类
- 牛客 小a与星际探索 bfs
- python 中的re模块,正则表达式
- 05-Mirrorgate数据库信息
- 洛谷P2446 大陆争霸
- 02linux 基本命令
- MySQL大数据量分页查询方法及其优化