技术标签: 算法 深度优先 c++ AcWing算法基础(C++代码)
DFS(Depth-First Search)
深度优先搜索,是一种常用的图遍历算法,用于在图或树数据结构中遍历所有节点。
深度优先搜索从一个起始节点开始,沿着一条路径尽可能远地访问节点,直到到达不能继续前进的节点,然后返回上一层继续探索其他路径。这个过程是递归的,通过不断地深入进入节点的子节点,直到遍历完整个图。
深度优先搜索使用栈(Stack)
数据结构来保存需要探索的节点。每次访问一个节点时,将其标记为已访问,并将其未访问的邻居节点压入栈中。然后从栈中弹出一个节点,继续访问该节点的未访问邻居节点,直到栈为空。
空间复杂度: O ( n ) O(n) O(n)
DFS不保证找到最短路径。因为它首先沿着一条路径尽可能远地深入。如果需要找到最短路径,可以考虑使用其他算法,如广度优先搜索(BFS)或 Dijkstra 算法。一般最小步数、最短距离、最小操作次数等问题采用BFS。思路奇怪或是对空间要求高的使用深度优先搜索(DFS)。
DFS 在解决许多图论问题和遍历问题上非常有用,如查找图中的路径、连通性检测、拓扑排序等。它也可以应用于树的遍历,例如先序遍历、中序遍历和后序遍历。
题目描述:
给定一个整数 n n n,将数字 1 ∼ n 1∼n 1∼n 排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式:
共一行,包含一个整数 n n n。
输出格式:
按字典序输出所有排列方案,每个方案占一行。
数据范围:
1 ≤ n ≤ 7 1≤n≤7 1≤n≤7
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
实现思路
代码实现:
1.使用bool类型数组来表示是否占用
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 10;
int n, path[N];
bool st[N]; // 状态数组
void dfs(int u) // 第几个数字,一共几个数字
{
if (u == n)// 递归到最后一个数字
{
for (int i = 0; i < n; i++) cout << path[i] << ' '; // 输出保存的结果
puts(" ");
}
for (int i = 1; i <= n; i++)
if (!st[i]) // 没有被用过的数
{
path[u] = i;
st[i] = true; // i被用过
dfs(u + 1);// 走到下一层
st[i] = false;// 恢复现场
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
dfs(0);
return 0;
}
2.使用整型变量补码的每位来表示是否占用
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 10;
int n, path[N];
void dfs(int u, int state) // 第几个数字,一共几个数字
{
if (u == n)// 递归到最后一个数字
{
for (int i = 0; i < n; i++) cout << path[i] << ' '; // 输出保存的结果
puts(" ");
}
for (int i = 0; i < n; i++)
if (!(state >> i & 1)) // 没有被用过的数
{
path[u] = i + 1;
dfs(u + 1, state + (1 << i));
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
dfs(0, 0);
return 0;
}
题目描述:
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n n n,请你输出所有的满足条件的棋子摆法。
输入格式共一行,包含整数 n n n。
输出格式:
每个解决方案占 n n n 行,每行输出一个长度为 n n n 的字符串,用来表示完整的棋盘状态。
其中, 表示某一个位置的方格状态为空, Q Q Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围:
1 ≤ n ≤ 9 1≤n≤9 1≤n≤9
输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
代码实现:
//在此处,为了模拟坐标轴,使用u替换y,使用i替换x
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N=20;//此处x轴和y轴的长度为10,开20是大了,但是对角线长度约1.414*10(根号2),所以数组开大有好处
int n;//此处存储输入的行数&列数,
char q[N][N];//构建棋盘,大一些没坏处,注意类型需要为char(一开始无语写了个int)
bool col[N],dg[N],udg[N];//col是Column(列)的缩写,dg是diagonal(对角)的缩写,(反对角线前面的u想不出了)
//设udg的方程为y=x+b则b=y-x,替换后b=u-i,防止出现负数,则加上n,则有b=u+n-i(其实b=n+i-u也可,目的是一个对角线能单独映射)
//设dg的方程为y=-x+b,b=y+x,替换后b=i+u,perfect
void dfs(int u){
//已经操作了u行
if(u==n){
//好家伙,已经操作完u行了,一个输出了
for(int i=0;i<n;i++){
cout<<q[i]<<endl;
}
cout<<endl;
/*这种写法也可,但是如果上面的看不懂建议补习C语言基础
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<q[i][j];
}
cout<<endl;
}
cout<<endl;
*/
return;
}
for(int i=0;i<n;i++){
//到这一步说明还没有dfs搜索完
if(!col[i] and !dg[i+u] and !udg[u+n-i]){
//这个点在各种映射下都是合法的
q[u][i]='Q';
col[i]=dg[i+u]=udg[u+n-i]=true;//这些点用掉啦
dfs(u+1);//继续往下一层探
q[u][i]='.';
col[i]=dg[i+u]=udg[u+n-i]=false;//出来后这些点恢复原状
}
}
}
int main(){
cin>>n;//输入行数
for(int i=0;i<n;i++){
//搭建一个“船新”的棋盘
for(int j=0;j<n;j++){
q[i][j]='.';
}
}
dfs(0);//0代表目前已经操作了0行,并且需要对第1行进行操作(在数组中映射为0行)
return 0;
}
文章浏览阅读127次。SCC(超级计算集群)简介 SCC概述 超级计算集群(Super Computing Cluster,SCC)使用高速RDMA网络互联的CPU以及GPU等异构加速设备,面向高性能计算、人工智能/机器学习、科学/工程计算、数据分析、音视频处理等应用,提供极致计算性能和并行效率的计算集群服务。SCC实例类型 类型 CPU Memory 网络 存储 适用场景 ecs.scch5.16xlarge 64核..._跨rdma网卡bond
文章浏览阅读1.2k次,点赞3次,收藏2次。音频采集量化概念1.采样大小(位深):一个采样用多少bit存放,常用的是16bit。2.采样率:采样频率,8K, 16K, 32K, 44.1K, 48K3.声道数:单声道,双声道,多声道码率计算PCM数据音频流码率=采样率x采样大小x声道数WAVWAV为微软公司(Microsoft)开发的一种声音文件格式,它符合RIFF(Resource Interchange File Format)文件规范,用于保存Windows平台的音频信息资源,被Windows平台及其应用程序所广泛支持。WAVE文_linux pcm short数组
文章浏览阅读648次。import java.util.concurrent.Exchanger;import java.util.concurrent.ExecutorService;import java.util.concurrent.Executors;public class ExchangerTest{ public static void main(String[] args) _exchanger类交换变量时值交换吗
文章浏览阅读1.2w次。mac安装双系统的坑安装环境:2017 macbook air 128g(是的,空间很小)macos 10.14.4准备:1。win10镜像。安装步骤为:1。打开boot camp2。分区3。安装出现错误:windows支持软件未能存储到所选驱动器,磁盘上没有足够的可用空间。删了很多东西,把win的分区加大都无法解决问题。折腾了很久终于找到了原因。原因:boot camp只认fat32,fat32..._bootcamp磁盘上没有足够的可用空间
文章浏览阅读509次。写在前面GDOI赛前集训Part2,今天结束了,当然作为一个弱菜,还是垫了一波底。_四会集训总结
文章浏览阅读2.9w次,点赞9次,收藏82次。大数据、数据分析、数据挖掘的区别是,大数据是互联网的海量数据挖掘,而数据挖掘更多是针对内部企业行业小众化的数据挖掘,数据分析就是进行做出针对性的分析和诊断,大数据需要分析的是趋势和发展,数据挖掘主要发现的是问题和诊断:1、大数据(big data):指无法在可承受的时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、..._大数据分析与数据挖掘
文章浏览阅读1.3k次。前言:_audio架构
文章浏览阅读836次。如何用python编写3D游戏_python 3d游戏开发
文章浏览阅读409次。思路是根据输入的P-sequence数来计算各个右括号的分级。只需统计右括号所属的括号对内(左侧,等级始终小于右括号等级) 的所有低一层(等级高1)右括号的W-sequence数,求和,加1即可得到当前右括号的W-sequence数,标记到当前的右括号上,无需还原整个括号结构。_c语言parencodings
文章浏览阅读215次。准备工作Tomcat6.0.29JDK6CAS Server版本:cas-server-3.5CAS Client版本:cas-client-3.1.12将cas-server-support-jdbc-3.5.1.jar 包拷贝到cas项目的lib目录下。一、配置数据源在WEB-INF/deployerConfigContext.xml最后位置加入 <..._cas 3.5.1 登录用户配置
文章浏览阅读2k次。我相信大家在生活中肯定每日都离不开图片的处理了,比如:考试报名、图片传送、网页图片上传的过程中,都或多或少遇到过“您上传的图片太大”的问题每次遇到这种情况是真的有点心塞,所以今天特别给大家带来一款人人必备的实用、超好用的开源优质免费神器,秒杀一片付费软件!开源神器,永久免费的图片压缩工具1资源简介名称:图压,软件支持MAC、Win 系统,软件界面清新、几乎可以做到无损画质压缩,图片处理速度快,且永久开源免费,小资源体验了下,真的好用到爆,所以来推荐给大家软件._.net图片压缩 开源类
文章浏览阅读2.4k次。欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定!对商业智能BI、大数据分析挖掘、机器学习,python,R等数据领域感兴趣的同学加微信:tstoutiao,邀请你进入数据爱好者交流群,数据..._r语言evalmod函数在哪个包