dfs 例题皇后问题
2024-08-30 06:13:22
题目描述
一个如下的 6 \times 66×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5 来描述,第 ii 个数字表示在第 ii 行的相应位置有一个棋子,如下:
行号 1\ 2\ 3\ 4\ 5\ 61 2 3 4 5 6
列号 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。
输入格式
一行一个正整数 nn,表示棋盘是 n \times nn×n 大小的。
输出格式
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
输入输出样例
输入 #1复制
6
输出 #1复制
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明/提示
【数据范围】
对于 100\%100% 的数据,6 \le n \le 136≤n≤13。
题目翻译来自NOCOW。
USACO Training Section 1.5
最近在了解dfs所以就用这个方法来做
在了解dfs算法的前提下我认为这道题最大的难点在于如何表示对角线;
先上代码:
#include<iostream>
using namespace std;
int n;
int tatal=;
int check[][];
int a[]; //数组a的次序代表皇后的次序,同时也代表行数,数组a是用来存储列数的
void print(){
for(int m=;m<=n;m++){
cout<<a[m]<<" ";
}
cout<<endl;
}
void dfs(int line){//line代表皇后的个数,同时也可以认为代表行,这样就避免了在同一行有重复的皇后
if(line>n){
if(tatal<){
print();
}
tatal++;
return;
}
for(int i=;i<=n;i++){
if((!check[][i])&&(!check[][i+line])&&(!check[][i-line+n])){
a[line]=i;
check[][i]=;
check[][i+line]=;
check[][i-line+n]=;
dfs(line+);
check[][i]=;
check[][i+line]=;
check[][i-line+n]=;
}
}
}
int main(){
cin>>n;
dfs();
cout<<tatal;
}
可以观察对角线上的格子和行和列有一定的规律,按照这种规律相对于斜对角线的数组来说每一个对角线都是一个确定的值,所以可以用line+i,line-i+n来标记斜对角线的数组
最新文章
- android性能优化练习:过度绘制
- 大规模IP地址黑名单高性能查询实现
- [修改后]html+css 做成一个可浏览的表格
- java笔记1
- cut mysqladmin
- sql插入删除表内字段基础操作
- GLES &; Shader Language 易错集锦
- CentOS 7 用户账户配置
- Python解析HTML的开发库pyquery
- [Unity3D]蓝港面试题
- css3处理sprite背景图压缩来解决H5网页在手机浏览器下图标模糊的问题
- Android SDCard Mount 流程分析
- vuex的简易入门
- jersey实现文件下载
- python calendar(日历)模块
- python学习:设计一个算法将缺失的数字找出来。
- HDU1560 DNA sequence IDA* + 强力剪枝 [kuangbin带你飞]专题二
- RX系列一 | ReactiveX根源 | 观察者模式分析
- Linux——目录和文件
- docker容器配置nginx负载均衡 -----加权