洛谷:P1219 [USACO1.5] 八皇后 Checker Challenge(dfs深度优先遍历求解)

本文主要是介绍洛谷:P1219 [USACO1.5] 八皇后 Checker Challenge(dfs深度优先遍历求解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

一个如下的 6×66×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 52 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 61 2 3 4 5 6

列号 2 4 6 1 3 52 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

输入格式

一行一个正整数 n,表示棋盘是 n×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入输出样例

输入 

6

输出

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

说明/提示

【数据范围】
对于 100%的数据,6≤n≤13。

解题思路:

从每一行开始,遍历一这行的所有元素,如果这一行的列,正对角,反对角都没有皇后,就在这个位置放入一个皇后,然后继续向下一行进行搜索。

对角坐标如下图:

(蓝色为正对角,绿色为反对角,

故正对角线的坐标为:当前行+当前列,

反对角坐标为:n-当前行+当前列。

代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
bool y[N], dg[N], udg[N]; //分别用于记录当前元素的这一列,正对角,反对角是否有元素
int n, ans;
int e[N][N];
void dfs(int u)  //深度优先遍历
{if (u == n) //当遍历到最后一行时结束{//如果成功搜索到最后一行,就说明已经找到了一个方案,就把这个方案输出if (ans < 3) //只输出3次结果{for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (e[i][j] == 1) cout << j + 1 << " ";}}cout << endl;}ans++;  //记录一共几条结果满足条件}for (int i = 0; i < n; i++){//遍历这一行当中得元素,如果这一列以及两个对角都没有皇后,就在这个坐标放入一个皇后if (!y[i] && !dg[u + i] && !udg[n - u + i]){e[u][i] = 1;y[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);//放完后继续向下一行搜索//搜索完之后回溯要把数据还原y[i] = dg[u + i] = udg[n - u + i] = false;e[u][i] = 0;}}
}
int main()
{cin >> n;dfs(0);cout << ans << endl;return 0;
}

模板题,可以看看n皇后dfs求解

n皇后问题(DFS)

算法小白的刷题日记。

这篇关于洛谷:P1219 [USACO1.5] 八皇后 Checker Challenge(dfs深度优先遍历求解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/689790

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操