热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

宽度优先搜索BFS,求解迷宫问题

宽度优先搜索(BFS)也是搜索的手段之一。它与深度优先搜索类似,从某个状态出发搜索所有可达的状态。与DFS不同的是搜索的顺序,宽度优先搜索总是先搜索离初始状态近的状态。也就是说,它是按照开始状态--

宽度优先搜索(BFS)也是搜索的手段之一。它与深度优先搜索类似,从某个状态出发搜索所有可达的状态。

与DFS不同的是搜索的顺序,宽度优先搜索总是先搜索离初始状态近的状态。也就是说,它是按照开始状态--->只需1次转移就可以到达的所有状态--->只需2次转移就可以到达的所有状态--->......,以这样的顺序开始搜索,对于同一个状态,宽度优先搜索只经过一次,因此时间复杂度:O(状态数 * 转移的方式)。

深度优先搜索隐式利用了栈进行计算(递归的基础便是栈),而宽度优先搜索则利用了队列。搜索时首先将初始状态添加到队列里,此后从队列的最前端不断取出状态,把从该状态可以转移到的状态中尚未访问过的部分加入队列,如此往复知道队列为空或找到问题的解。

队列的特性为先进先出,那么我们就可以知道所有的状态都是按照初始状态由近及远的顺序被遍历的。

迷宫问题:

给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格
的通道移动。请求出从起点到终点所需的最小步数。请注意,本题假定从起点一定可以移动
到终点。

输入
N=10, M=10(迷宫如下图所示。'#','.','S','G'分别表示墙壁、通道、起点和终点)
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出
22

分析:起点状态其实就对应初始状态,起点可走周围四个方向(过程中需对是否越界,是否撞墙做出判断,不满足条件都为不可到达的状态),一旦遍历的点为终点这时经历的路径必为最短,因为宽度优先搜索是由近到远的,所以第一个来到终点的路径必为最短。过程中用二维数组d将到达每个点的最短路径保存下来。

由于要向四个方向移动,用dx和dy两个数组来表示四个方向向量。

#include
#include

#include

using namespace std;
#define INF 0x3f3f3f3f
typedef pair
<int,int> P;
const int MAX = 100;
char maze[MAX][MAX+1];
int m,n;
int sx,sy;//起点坐标
int gx,gy;//终点坐标

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int d[MAX][MAX+1];

int bfs(){
queue

que;
//寻找起点和终点坐标
for(int i=0;i){
for(int j=0;j){
if(maze[i][j]=='S'){
sx
=i;sy=j;
}
if(maze[i][j]=='G'){
gx
=i;gy=j;
}
}
}

memset(d,INF,
sizeof(d));
//将初始状态(起点)加入队列
que.push(P(sx,sy));
d[sx][sy]
=0;
while(que.size()){
//取出队头
P p = que.front();
que.pop();
int nx=p.first,ny=p.second;
if(nx==gx&&ny==gy){
break;
}
for(int i=0;i<4;i++){
//移动后的位置记为(nx,ny)
nx=p.first + dx[i];ny=p.second + dy[i];
if(nx>=0&&ny>=0&&nx'#'){
d[nx][ny]
=d[p.first][p.second]+1;
que.push(P(nx,ny));
}
}
}
return d[gx][gy];
}

int main(){
cin
>>m>>n;
for(int i=0;i){
cin>>maze[i];
}
cout
<endl;
// cout<// cout<
return 0;
}

 


推荐阅读
  • 本文讨论了一个数列求和问题,该数列按照一定规律生成。通过观察数列的规律,我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和,其中f[i]表示数列中有i个数字。根据参考的思路,我们可以将算法的时间复杂度控制在O(n),即计算到5e5即可满足1e9的要求。 ... [详细]
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • 李逍遥寻找仙药的迷阵之旅
    本文讲述了少年李逍遥为了救治婶婶的病情,前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵,有些方格内有怪物,有些方格是安全的。李逍遥需要避开有怪物的方格,并经过最少的方格,找到仙药。在寻找的过程中,他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • JVM 学习总结(三)——对象存活判定算法的两种实现
    本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法:引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活,虽然简单高效,但无法解决循环引用的问题;可达性分析算法通过判断对象是否可达来确定存活对象,是主流的Java虚拟机内存管理算法。 ... [详细]
  • 本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体,实现了入队和出队操作,并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • 本文介绍了UVALive6575题目Odd and Even Zeroes的解法,使用了数位dp和找规律的方法。阶乘的定义和性质被介绍,并给出了一些例子。其中,部分阶乘的尾零个数为奇数,部分为偶数。 ... [详细]
  • 本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes,通过状压和spfa算法解决了这个问题。给定一个有向图,求在不超过m步的情况下,能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]
  • STL迭代器的种类及其功能介绍
    本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系,并详细描述了各个迭代器的功能和使用方法。其中,输入迭代器用于从容器中读取元素,输出迭代器用于向容器中写入元素,正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]
  • 深入解析Linux下的I/O多路转接epoll技术
    本文深入解析了Linux下的I/O多路转接epoll技术,介绍了select和poll函数的问题,以及epoll函数的设计和优点。同时讲解了epoll函数的使用方法,包括epoll_create和epoll_ctl两个系统调用。 ... [详细]
  • 本文介绍了一道经典的状态压缩题目——关灯问题2,并提供了解决该问题的算法思路。通过使用二进制表示灯的状态,并枚举所有可能的状态,可以求解出最少按按钮的次数,从而将所有灯关掉。本文还对状压和位运算进行了解释,并指出了该方法的适用性和局限性。 ... [详细]
  • BZOJ1233 干草堆单调队列优化DP
    本文介绍了一个关于干草堆摆放的问题,通过使用单调队列来优化DP算法,求解最多可以叠几层干草堆。具体的解题思路和转移方程在文章中进行了详细说明,并给出了相应的代码示例。 ... [详细]
  • 向QTextEdit拖放文件的方法及实现步骤
    本文介绍了在使用QTextEdit时如何实现拖放文件的功能,包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数,并结合QMimeData和QUrl等类,可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]
  • IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]
  • 深入理解Kafka服务端请求队列中请求的处理
    本文深入分析了Kafka服务端请求队列中请求的处理过程,详细介绍了请求的封装和放入请求队列的过程,以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析,帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]
author-avatar
郑geraghty_926
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有