迷宫问题
题目描述
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
样例输入
1
5 5
S-###
-----
##---
E#---
---##
样例输出
9
1 #include<stdio.h>
2 #include<
string.h>
3 #include<queue>
4 #include<iostream>
5 using namespace std;
6 struct N
//结构体定义了2个信息:
7 {
8 int x,y;
//结点编号
9 int step;
//步数
10 } p[
105];
11 char map[
105][
105];
12 int vis[
105][
105];
13 int dir[
4][
2]= {{-
1,
0},{
0,-
1},{
1,
0},{
0,
1}};
14 int n,m,sx,sy,ex,ey,ans;
15 bool check(
int x,
int y)
16 {
17 if(x>=
0 && x<m && y>=
0 && y<n&&vis[x][y]==
0&& map[x][y]!=
'#')
18 return true;
19 return false;
20 }
21 void bfs()
22 {
23 queue<N> Q;
//定义一个队列
24 N a;
25 N next;
26 a.x =
sx;
27 a.y =
sy;
28 a.step =
0;
//结点编号、步数初始化
29 vis[a.x][a.y]=
1;
//记录此结点是否遍历过
30 Q.push(a);
//起始点放入队列
31 while(!Q.empty())
//当队列不为空
32 {
33 a = Q.front();
//取出队头结点
34 Q.pop();
35 for(
int i =
0; i<
4; i++
)
36 {
37 next =
a;
38 next.x+=dir[i][
0];
39 next.y+=dir[i][
1];
//向其余方向遍历
40 next.step=a.step+
1;
41 if(next.x==ex&&next.y==ey)
//若它是所求的目标状态，跳出循环
42 {
43 ans =
next.step;
44 return ;
45 }
46 if(check(next.x,next.y))
47 {
48 vis[next.x][next.y] =
1;
49 Q.push(next);
//扩展出子结点、依次添到到队尾
50 }
51
52 }
53 }
54 ans = -
1;
//找不到目标、输出-1.
55 }
56 int main()
57 {
58 int t;
59 int w;
60 scanf(
"%d",&
t);
61 while(t--
)
62 {
63 memset(vis,
0,
sizeof(vis));
64 scanf(
"%d%d",&m,&
n);
65 int i,j;
66 for(i =
0; i<m; i++
)
67 for(j=
0; j<n; j++
)
68 cin>>
map[i][j];
69 for(i =
0; i<m; i++
)
70 for(j =
0; j<n; j++
)
71 {
72 if(map[i][j]==
'S')
73 {
74 sx =
i;
75 sy =
j;
76 //标记起始位置
77 }
78 else if(map[i][j]==
'E')
79 {
80 ex=
i;
81 ey=
j;
82 //标记结束位置
83 }
84 }
85 bfs();
86 printf(
"%d\n",ans);
87 }
88 return 0;
89 }
View Code
转载于:https://www.cnblogs.com/qing123tian/p/11107487.html
相关资源：迷宫问题实现
