BFS广搜解决迷宫问题java实现
目录
1.例题
题目描述
迷宫由 n 行 m 列的单元格组成,每个单元格要么是空地,要么是障碍物。其中1表示空地,可以走通,2表示障碍物。给定起点坐标startx,starty以及终点坐标endx,endy。现请你找到一条从起点到终点的最短路径长度。
输入
第一行包含两个整数n,m(1<=n,m<=1000)。接下来 n 行,每行包含m个整数(值1或2),用于表示这个二维迷宫。接下来一行包含四个整数startx,starty,endx,endy,分别表示起点坐标和终点坐标。
输出
如果可以从给定的起点到终点,输出最短路径长度,否则输出NO。
测试数据
输入
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
输出
7
2. 思路分析
基本思想
这道题属于一道较为经典的BFS图的广度优先搜索算法例题。类似于一个分层搜索的过程,广度优先搜索需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序访问这些结点的邻接结点。即从给定的起点开始向四周扩散,判断是否能够到达终点,如果不能,就继续BFS广搜,直到能够到达终点或者将所有结点遍历完一遍。在搜索前定义一个flag变量用来标记是否到达终点。
具体步骤
1)访问初始结点 p 并标记结点 p 为已访问。
2)结点 p 入队列
3)当队列非空时,继续执行,否则算法结束。
4)出队列取得队头结点 first
5)查找结点 first 的第一个方向的邻接结点 newp 。
6)若结点 first 的邻接结点 newp 不存在,则转到步骤3:否则循环执行以下三个步骤:
6.1若结点 newp 尚未被访问并且可以走通,则访问结点 newp 并标记为已访问。
6.2结点 newp 入队列
6.3查找结点 first 的继 newp 邻接结点后的下个邻接结点 newp .转到步骤6
代码实现
3.BFS小结
求解思路:
将队首结点可拓展的点入队,如果没有可拓展的点,将队首结点出队。重复以上步骤,直到到达目标位置或者队列为空。
注意
bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了,bfs传回的是经过 边数 最少的解,但是因为加权了,这个解到根节点的 距离 不一定最短。 比如1000+1000是只有两段,1+1+1+1有4段,由于bfs返回的经过边数最少的解,这里会返回总长度2000的那个解,显然不是距离最短的路径 。BFS 运用到了队列。
- 点赞
- 收藏
- 关注作者

评论(0)