问题 1672: 迷宫问题（BFS）

题目链接：https://www.dotcpp.com/oj/problem1672.html

问题 1672: 迷宫问题

时间限制: 1Sec 内存限制: 32MB 提交: 663 解决: 158

题目描述

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

输入

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

宽度优先搜索的常规题，但是需要注意判断：如果不存在通路需要返回-1（否则只能过50%，存在一半的数据）；

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath> 
 4 #include <string>
 5 #include <cstring>
 6 #include <map> 
 7 #include <cstdio>
 8 #include <queue>
 9 using namespace std;
10 const int INF=0x3f3f3f3f;
11 typedef pair<int,int> P; 
12 char maze[105][105];
13 int N,M;
14 int sx,sy;
15 int gx,gy;
16 int d[105][105];
17 int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
18 int t;
19 int bfs()
20 {
21     queue<P> que;
22     for(int i=0;i<N;i++){
23         for(int j=0;j<M;j++){
24             d[i][j]=INF;
25         }
26     }
27     que.push(P(sx,sy));
28     d[sx][sy]=0;
29     while(que.size()){
30         P p=que.front();
31         que.pop();
32         if(p.first==gx&&p.second==gy) break;
33         for(int i=0;i<4;i++){
34             int nx=p.first+dx[i],ny=p.second+dy[i];
35             if(nx>=0&&nx<N&&ny>=0&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF){
36                 que.push(P(nx,ny));
37                 d[nx][ny]=d[p.first][p.second]+1;
38             }
39         }
40     }
41     if(d[gx][gy]==INF) return -1;
42     else return d[gx][gy];
43 }
44 int main()
45 {
46     while(cin>>t){
47         while(t--){
48             cin>>N>>M;
49             for(int i=0;i<N;i++){
50                 for(int j=0;j<M;j++){
51                     cin>>maze[i][j];
52                     if(maze[i][j]=='S'){
53                         sx=i;
54                         sy=j;
55                     }
56                     if(maze[i][j]=='E'){
57                         gx=i;
58                         gy=j;
59                     }
60                 }
61             }
62             cout<<bfs()<<endl;
63         }
64     }
65     return 0;
66 }

。。。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <cstring>
 5 #include <queue>
 6 using namespace std;
 7 const int INF=0x3f3f3f3f;
 8 typedef pair<int,int> P;
 9 int t,n;
10 int N,M;
11 int d[105][105];
12 char a[105][105];
13 int dx[4]={1,-1,0,0};
14 int dy[4]={0,0,1,-1};
15 int sx,sy,gx,gy;
16 int x,y,nx,ny;
17 int bfs()
18 {
19     memset(d,INF,sizeof(d));
20     queue<P> que;
21     que.push(P(sx,sy));
22     d[sx][sy]=0;
23     while(!que.empty()){
24         P p=que.front();
25         que.pop();
26         x=p.first,y=p.second;
27         if(x==gx&&y==gy) break;
28         for(int i=0;i<4;i++){
29             nx=x+dx[i],ny=y+dy[i];
30             if(nx>=0&&nx<N&&ny>=0&&ny<M&&a[nx][ny]!='#'&&d[nx][ny]==INF){
31                 que.push(P(nx,ny));
32                 d[nx][ny]=d[x][y]+1;
33             }
34         }
35     }
36     if(d[gx][gy]==INF) return -1;
37     return d[gx][gy];
38 }
39 int main()
40 {
41     while(cin>>t){
42         while(t--){
43             cin>>N>>M;
44             for(int i=0;i<N;i++){
45                 for(int j=0;j<M;j++){
46                     cin>>a[i][j];
47                     if(a[i][j]=='S'){
48                         sx=i,sy=j;
49                     }else if(a[i][j]=='E'){
50                         gx=i,gy=j;
51                     }
52                 }
53             }
54             cout<<bfs()<<endl;
55         }
56     }
57     return 0;
58 }

问题 1672: 迷宫问题 （BFS）

问题 1672: 迷宫问题（BFS）