【搜索算法】 跳马问题(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了,耗时也比较少。

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

目录
打赏
0
0
0
0
1
分享
相关文章
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
52 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
81 1
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
1156 0
高精度算法(加、减、乘、除,使用c++实现)

热门文章

最新文章