一、问题引入
有一天,小哈一个人去玩迷宫。但是方向感不好的小哈很快就迷路了。小哼得知后便去解救无助的小哈。此时的小哼已经弄清楚了迷宫的地图,现在小哼要以最快的速度去解救小哈。那么,问题来了...
二、问题的分析
首先我们用一个二维数组来存储这个迷宫,刚开始的时候,小哼处于迷宫的入口处(1,1),小哈在(p,q)。其实这道题的的本质就在于找从(1,1)到(p,q)的最短路径。
此时摆在小哼面前的路有两条,我们可以先让小哼往右边走,直到走不通的时候再回到这里,再去尝试另外一个方向。
在这里我们规定一个顺序,按照顺时针的方向来尝试(即右→下→左→上)。
我们先来看看小哼一步之内可以到达的点有哪些?只有(1,2)和(2,1)。
根据刚才的策略,我们先往右边走,但右边(1,3)有障碍物,所以只能往下(2,2)这个点走。但是小哈并不在(2,2)这个点上,所以小哼还得继续往下走,直至无路可走或者找到小哈为止。
注意:并不是让我们找到小哈此题就解决了。因为刚才只是尝试了一条路的走法,而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择,因此我们需要返回到这些地方继续尝试往别的方向走,直到把所有可能都尝试一遍,最后输出最短的一条路径。
例如下图就是一条可行的搜索路径:
三、解决问题——深度优先搜索
(1)如何写dfs函数。
dfs函数的功能是解决当前应该怎么办。而小哼处在某个点的时候需要处理的是:先检查小哼是否已经到达小哈的位置,如果没有到达则找出下一步可以走的地方。
为了解决这个问题,此处dfs()函数只需要维护三个参数,分别是当前这个点的x坐标,y坐标以及当前已经走过的步数step。
//dfs函数定义如下:
void dfs(int x,int y,int step)
{
return ;
}
(2)判断是否已经到达小哈的位置。
只需要判断当前的坐标是否与小哈的坐标相等就可以了,如果相等就标明已经到达小哈的位置。
void dfs(int x,int y,int step)
{
if(x==p && y==q) //判断是否到达小哈的位置
{
if(step<min)
min=step; //更新最小值
return; //这步很重要!
}
return ;
}
(3)如何获得下一个方向的坐标(此处定义一个方向数组)。
int next[][]={
{,},//向右走
{,},//向下走
{,-},//向左走
{-,},//向上走
};
通过这个方向数组,使用循环就可以方便地得到下一步的坐标。
这里将下一步的横坐标用tx存储,纵坐标用ty存储。
for(k=;k<=;k++)
{
/*计算下一个点的坐标*/
tx=x+next[k][];
ty=y+next[k][];
}
(4)对下一个点(tx,ty)进行判断(是否越界,是否有障碍物,是否已经在路径中)。
在这里我们用book[tx][ty]来记录格子[tx][ty]是否已经在路径中。
如果这个点符合所有的要求,就对这个点进行下一步的扩展,即dfs(tx,ty,step+1)。
注意这里是step+1,因为一旦从这个点开始继续往下尝试,就意味着步数已经增加了1。
for(k=;k<=;k++)
{
/*计算下一个点的坐标*/
tx=x+next[k][];
ty=y+next[k][];
if(tx< || tx>n || ty< || ty>m) //判断是否越界
continue;
/*判断该点是否为障碍物或者已经在路径中*/
if(a[tx][ty]== && book[tx][ty]==)
{
book[tx][ty]=; //标记这个点已经走过
dfs(tx,ty,step+); //开始尝试下一个点
book[tx][ty]=; //尝试结束,取消这个点的标记
}
}
四、完整代码
#include<stdio.h>
int n,m,p,q,min=;
int a[][],book[][];
void dfs(int x,int y,int step)
{
int next[][]={
{,},//向右走
{,},//向下走
{,-},//向左走
{-,},//向上走
};
int tx,ty,k;
if(x==p && y==q) //判断是否到达小哈的位置
{
if(step<min)
min=step; //更新最小值
return;
}
/*枚举四种走法*/
for(k=;k<=;k++)
{
/*计算下一个点的坐标*/
tx=x+next[k][];
ty=y+next[k][];
if(tx< || tx>n || ty< || ty>m) //判断是否越界
continue;
/*判断该点是否为障碍物或者已经在路径中*/
if(a[tx][ty]== && book[tx][ty]==)
{
book[tx][ty]=; //标记这个点已经走过
dfs(tx,ty,step+); //开始尝试下一个点
book[tx][ty]=; //尝试结束,取消这个点的标记
}
}
return;
} int main()
{
int i,j,startx,starty;
scanf("%d %d",&n,&m); //读入n和m,n为行,m为列
/*读入迷宫*/
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d %d %d %d",&startx,&starty,&p,&q); //读入起点和终点坐标
/*从起点开始搜索*/
book[startx][starty]=; //标记起点已经在路径中,防止后面重复走
dfs(startx,starty,); //第一个参数是起点的x坐标,以此类推是起点的y坐标,初始步数为0
printf("%d",min); //输出最短步数
return ;
}
五、写在最后
发明深度优先算法的是John E.Hopcroft 和 Robert E.Tarjan。他们并不是研究全排列或者迷宫问题时发明了这个算法。
1971~1972年,他们在斯坦福大学研究图的连通性(任意两点是否可以相互到达)和平面性(图中所有的边相互不交叉。在电路板上设计布线的时候,要求线与线不能交叉,这就是平面性的一个实际应用),发明了这个算法。他们也因此获得了1986年的图灵奖。
在授奖仪式上,当年全国象棋程序比赛的优胜者说他的程序用的就是深度优先搜索算法,这是以其制胜的关键。
通过本次学习,我明白了当我们遇到这种需要“分身”,需要不断尝试完成的事情时,可以尝试使用深度优先搜索算法,因为计算机的运算速度还是很强的,我们要借助他的优势,完成一些生活中比较繁琐重复的事情。
(注:文章内容源自 啊哈磊的《啊哈算法》——很有意思的一本算法入门书!)
解救小哈——DFS算法举例的更多相关文章
-
解救小哈——dfs深搜
问题描述: 小哈去玩迷宫,结果迷路了,小哼去救小哈.迷宫由n行m列的单元格组成(n和m都小于等于50),每个单元格要么是空地,要么是障碍物. 问题:帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径 ...
-
啊哈算法之宽搜BFS解救小哈
简述 本算法摘选自啊哈磊所著的<啊哈!算法>第四章第三节的题目——BFS算法再次解救小哈.文中代码使用C语言编写,博主通过阅读和理解,重新由Java代码实现了一遍,以此来理解BFS算法.关 ...
-
BFS/DFS算法介绍与实现(转)
广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep-First-Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索.其中有很多的算法都用到了这两种思想,比 ...
-
图结构练习——判断给定图是否存在合法拓扑序列(dfs算法(第一个代码),邻接矩阵(前两个代码),邻接表(第三个代码))
sdut 2140 图结构练习——判断给定图是否存在合法拓扑序列 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描述 给定一个有向图 ...
-
DFS算法(——模板习题与总结)
首先,需要说明的是搜索算法本质上也是枚举的一种,时间复杂度还是很高的,遇到问题(特别是有水平的比赛上),不要优先使用搜索算法. 这里总结一下DFS算法: 1.从图中某个顶点出发,访问v. 2.找出刚访 ...
-
DFS 算法总结
DFS 算法总结 这篇文章会对DFS进行一个总结,列举的题目则是从LeetCode上面选的: 适用场景: 有三个方面,分别是输入数据.状态转换图.求解目标: 输入数据:如果是递归数据结构,如单链表,二 ...
-
2018-02-03-PY3下经典数据集iris的机器学习算法举例-零基础
---layout: posttitle: 2018-02-03-PY3下经典数据集iris的机器学习算法举例-零基础key: 20180203tags: 机器学习 ML IRIS python3mo ...
-
UVA 291 The House Of Santa Claus(DFS算法)
题意:从 节点1出发,一笔画出 圣诞老人的家(所谓一笔画,就是遍访所有边且每条边仅访问一次). 思路:深度优先搜索(DFS算法) #include<iostream> #include&l ...
-
POJ 3620 Avoid The Lakes(dfs算法)
题意:给出一个农田的图,n行m列,再给出k个被淹没的坐标( i , j ).求出其中相连的被淹没的农田的最大范围. 思路:dfs算法 代码: #include<iostream> #inc ...
随机推荐
-
一个不错的vim配置
set nocp set backspace=indent,eol,start set number set autoindent set nocompatible set bs=indent,eol ...
-
SpringDataMongoDB介绍(二)-MongoOperations介绍
MongoOperations是一个很强大的接口,有了这个接口,基本上什么都搞定了. 其介绍 Interface that specifies a basic set of MongoDB opera ...
-
FOR 循环 索引从n 开始
RF 中FOR 循环默认是从0开始,如果想从任意n开始如下所示: 方法一: 结果,如你所愿输出1-6: 方法二,利用FOR遍历list来实现: 结果: 这里注意是输出1-9而不是1-10
-
C#总结(二)事件Event 介绍总结
最近在总结一些基础的东西,主要是学起来很难懂,但是在日常又有可能会经常用到的东西.前面介绍了 C# 的 AutoResetEvent的使用介绍, 这次介绍事件(event). 事件(event),对于 ...
-
Web应用安全测试
偷偷挪用人家的分享: https://blog.csdn.net/aojie80/article/details/43836521 写的很棒 Burp Suite 介绍 https://blog.cs ...
-
【LOJ#2542】[PKUWC2018]随机游走(min-max容斥,动态规划)
[LOJ#2542][PKUWC2018]随机游走(min-max容斥,动态规划) 题面 LOJ 题解 很明显,要求的东西可以很容易的进行\(min-max\)容斥,那么转为求集合的\(min\). ...
-
datatables弹窗报错信息屏蔽方法
在使用datatables的时候,总是会弹出这样的warning: Error: DataTables warning: table id=data_table- Requested unknown ...
-
BZOJ 2810 [Apio2012]kunai
Orz Starria 现在看来,也不是很难,能做...就是不能写 可以想到维护每个苦无扫过的矩形,然后做矩形面积并即可. 然后发现自己只会$n^2$的处理方法... 想了好久之后问了一发 Starr ...
-
Django 2.0.1 官方文档翻译: 编写你的第一个 Django app,第二部分(Page 7)
编写你的第一个 Django app,第二部分(Page 7)转载请注明链接地址 本教程上接前面的教程.我们会配置数据,创建你的第一个 model,并对Django 自动生成的 admin 站点进行快 ...
-
高性能分布式锁-redisson的使用
1,概述:在一些高并发的场景中,比如秒杀,抢票,抢购这些场景,都存在对核心资源,商品库存的争夺,控制不好,库存数量可能被减少到负数,出现超卖的情况,或者 产生唯一的一个递增ID,由于web应用部署在多 ...