迷宫的最短路径

  • 广度优先搜索,利用队列实现,类似与二叉树的层次遍历
  • 深度优先搜索,利用实现,可以通过递归来实现DFS,类似与二叉树的前/中/后序遍历

题目

对于一个N*M的迷宫,找出从起点B终点E的最短路径,假设存在B到E的最短路径

题目分析

最短路径,符合BFS的特点,–>总是先搜索距离起点近的状态

  • 已知起点终点坐标
  • 在迷宫的每一点有四种状态(方向)
  • 借助队列,没遍历一点,则将下一步所可能出现的有效的状态添加到队列中

何为有效的状态?

对于本问题,未被遍历过的点,可被访问的点(不是围墙),为有效的状态

因此,为了区别是否有效,需要一种机制来判断是否之前被访问过
本题中,现将距离数组d所有的元素初始化为INF最大值,每当遍历一个元素,则更新距离数组的值,(即距离加一)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <queue>


using namespace std;

char maze[10][10] = {
'#','B','#','#','#','#','#','#','.','#',
'.','.','.','.','.','.','#','.','.','#',
'.','#','.','#','#','.','#','#','.','#',
'.','#','.','.','.','.','.','.','.','.',
'#','#','.','#','#','.','#','#','#','#',
'.','.','.','.','#','.','.','.','.','#',
'.','#','#','#','#','#','#','#','.','#',
'.','.','.','.','#','.','.','.','.','.',
'.','#','#','#','#','.','#','#','#','.',
'.','.','.','.','#','.','.','.','E','#',
};
int M = 10;
int N = 10;
//起点坐标
int bx = 0;
int by = 1;
//终点坐标
int ex = 9;
int ey = 8;
int direction_x[4] = {-1,0,1,0};
int direction_y[4] = {0,1,0,-1};
const int INF = 100000000;
typedef pair<int, int> P;
// 记录当前位置距离起点最短距离,默认为最大值INF
int d[10][10] ;

int bfs(){
//初始化d数组
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
d[i][j] = INF;
}
}
//创建队列
queue<P> que;

que.push(P(bx,by));
d[bx][by] = 0;

//遍历队列

while( que.size() ){
P p = que.front();
que.pop();
if(p.first==ex and p.second==ey){
return d[ex][ey];
}

// 遍历四个方向,将合适的传入队列
for(int i=0;i<4;i++){
int point_x = direction_x[i] + p.first;
int point_y = direction_y[i] + p.second;

if (point_x<0 || point_y<0 || point_x>=M || point_y>=N || d[point_x][point_y]!=INF || maze[point_x][point_y]=='#'){
continue;
}
que.push(P(point_x,point_y));
d[point_x][point_y] = d[p.first][p.second] + 1;
}
}
return d[ex][ey];
}


int main() {
int res = bfs();
cout<<res<<endl;
return 0;
}

结果

1
22

本文标题:迷宫的最短路径

文章作者:定。

发布时间:2017年8月25日 - 22时08分

本文字数:2,320字

原始链接:http://cocofe.cn/2017/08/25/迷宫的最短路径/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。