【搜索算法】 跳马问题(C/C++)

简介: 【搜索算法】 跳马问题(C/C++)

搜索算法介绍

DFS:

深度优先搜索(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支,直到找到目标节点或达到叶节点(没有子节点的节点),然后回溯到上一个分支继续搜索。DFS可以用于许多问题比如路径寻找、连通性验证、拓扑排序等。

在ACM、蓝桥杯等著名竞赛中DFS算法是比较重要的,特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。DFS算法在OI赛中用处非常大,可以通过DFS/BFS暴力的方式可以拿到部分分数,蓝桥杯一般可以拿到20%的分数,有的甚至高达50%,是暴力得分的不二之选。

基本步骤:

DFS通常使用递归或栈来实现。以下是DFS的基本步骤:

选择起始点:选择图中的一个点作为起始点。

访问节点:标记起始节点为已访问,并将该节点加入递归或栈中。

探索邻接节点:从该点周围取出一个点,检查它的所有未访问的邻接节点。

递归或迭代:对每个未访问的邻接节点,将其标记为已访问,然后将其推入递归或栈中。

回溯:当当前节点的所有邻接节点都被访问后,递归中回溯/从栈中弹出该节点,继续搜索上一个点的其他分支。

结束条件:当栈为空或找到目标节点时,搜索结束。


BFS:

广度优先搜索(Breadth-First Search,简称BFS)是一种遍历或搜索树和图的算法,也称为宽度优先搜索,BFS算法从图的某个节点开始,依次对其所有相邻节点进行探索和遍历,然后再对这些相邻节点的相邻节点进行探索,直到遍历完所有的节点。BFS算法使用队列来辅助实现,将起始节点放入队列中,然后依次取出队列中的节点,访问其相邻节点,并将其加入队列。这样可以保证从起始节点出发,依次按照距离顺序遍历节点。BFS常用于寻找最短路径,因为它按照从起点到每个节点的距离来探索节点。

在ACM、蓝桥杯等著名竞赛中BFS算法是比较重要的,特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。BFS算法在OI赛中用处非常大,可以通过DFS/BFS暴力的方式可以拿到部分分数,蓝桥杯一般可以拿到20%的分数,有的甚至高达50%,是暴力得分的不二之选。

基本步骤:

BFS算法通常使用队列来实现,BFS算法的具体步骤如下:

创建一个队列,将起始节点加入队列;

创建一个集合,用于存储已经访问过的节点;

从队列中取出一个节点,并将其标记为已访问;

访问该节点的所有相邻节点,如果相邻节点未被访问,则将其加入队列;

重复步骤3和步骤4,直到队列为空。

BFS算法可以用来解决一些问题,例如图的遍历、最短路径搜索等。由于BFS算法保证了按照距离顺序遍历节点,因此可以用来寻找最短路径。另外,BFS算法还可以用来判断图是否连通,即从一个节点是否可以到达另一个节点。

动图算法

红色遍历为BFS宽度优先搜索,黄色为DFS深度优先搜索,绿色为起点,紫色为终点,黑色为障碍物)。


棋盘跳马问题

问题描述

  一个8×8的棋盘上有一个马初始位置为(a,b),他想跳到(c,d),问是否可以?如果可以,最少要跳几步?

输入格式

  一行四个数字a,b,c,d。

输出格式

  如果跳不到,输出-1;否则输出最少跳到的步数。

样例输入

1 1 2 3

样例输出

1

数据规模和约定

  0<a,b,c,d≤8且都是整数。

算法思路:

这道题是经典的跳马搜素问题,可以选择BFS、DFS,BFS用时会小一点,毕竟DFS会回溯。但是还是dfs好理解,dfs做此类题目还是最经典的,我们可以按照dfs上面所说的步骤进行写算法,思路还是很清晰的,具体的详解写在了代码上了。

算法实现:

#include<iostream>
using namespace std;
int a,b,c,d;
int vis[10][10];//标记数组
int sum=64;//能到达的方法数,最大为8*8的格子全部走一遍,初始值为8*8,因为要找最小值
int dx[]={1,1,-1,-1,2,2,-2,-2};//方向数组X
int dy[]={2,-2,2,-2,1,-1,1,-1};//方向数组Y
void dfs(int x,int y,int dep){//dfs搜索
  if(dep>=sum){//如果当前步数大于最小步数则没有意义继续搜下去了,直接return
    return;
  }
  if(x==c&&y==d){//到达终点坐标(c,d)
    if(dep<sum){//判断步数是否小于最小步数,小于就更新
      sum=dep;
    }
    return;
  }
  for(int i=0;i<8;i++){//8个方向搜索
    int bx=x+dx[i];
    int by=y+dy[i];
    if(vis[bx][by]==1){//已经走过就不走了
      continue;
    }
    if(bx<=0||bx>8||by<=0||by>8){//不在边界范围内也不走
      continue;
    }//判断完说明该点可以走
    vis[bx][by]=1;//走就标记为走过
    dfs(bx,by,dep+1);//继续dfs
    vis[bx][by]=0;//回溯,解标记
  }
}
int main(){
  cin>>a>>b>>c>>d;
  vis[a][b]=1;//先把起点标记为走过,不然对后面搜索有影响
  dfs(a,b,0);//起点开始搜索
  if(sum==64){//如果sum还等于64,就说明sum就没有被更新过,也就是说根本到达不了终点
    cout<<-1;
  }else{
    cout<<sum;
  }
  return 0;
}

最后,博主也去提交验证了一下,AC了,耗时也比较少。

本人小白一枚,能力有限,希望各位大佬理解。本文有错误的地方请指出,共同进步。执笔至此,感触彼多,全文将至,落笔为终,感谢大家的支持。

相关文章
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
90 2
|
5月前
|
存储 算法 调度
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
148 24
|
5月前
|
人工智能 自然语言处理 算法
阿里云 AI 搜索开放平台:从算法到业务——AI 搜索驱动企业智能化升级
本文介绍了阿里云 AI 搜索开放平台的技术的特点及其在各行业的应用。
560 3
|
6月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
156 15
|
6月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
2月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
107 0
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
56 0
|
4月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
123 17
|
3月前
|
机器学习/深度学习 算法 数据可视化
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
103 0
|
3月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
71 0