迷宫问题

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入

输入包含多组测试数据。输入的第一行是一个整数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