pair求解迷宫的最短路径(bfs)

题目描述:

问题：给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。

限制条件：N, M ≦100

示例输入：
10 10
#S######.# 
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
 

示例输出：
22

 1 pair类型可以构造明确模板pair<T,U>对象，对组pair定义成结构体struct,而非类class
 2 pair获取第一个成员，可以使用first;
 3     获取第二个成员，可以使用second；
 4 
 5 pair在头文件<utility>中，声明如下:
 6 template <class Type1, class Type2> struct pair
 7 {
 8     typedef Type1 first_type;
 9     typedef Type2 second_type;
10     Type1 first;
11     Type2 second;
12     pair();
13     pair(const Type1& x, const Type2& y);
14     template <class a, class b> pair(const pair<a,b>& _Right);   
15 }
16 
17 make_pair()模板函数无需写型别，就可以生成一个pair对象,即将两个值作为一个pair对象参数来传递
18 std::make_pair(42,'#');
19 std::pair<int ,char>(42,'#');

 1 /*
 2 问题：给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，
 3 每一步可以向邻接的上下左右四格的通道移动。请求出从起
 4 点到终点所需的最小步数。请注意，本题假定从起点一定可
 5 以移动到终点。
 6 限制条件：N, M ≦100
 7 
 8 示例输入：
 9 10 10
10 #S######.# 
11 ......#..#
12 .#.##.##.#
13 .#........
14 ##.##.####
15 ....#....#
16 .#######.#
17 ....#.....
18 .####.###.
19 ....#...G#
20 
21 示例输出：
22 22
23 */
24 
25 #include <iostream>
26 #include <queue>
27 #include <utility>
28 using namespace std;
29 const int INF=1e8;
30 const int MAXN=1005;
31 int sx,sy;   //起点坐标
32 int gx,gy;   //终点坐标
33 char a[MAXN][MAXN];  //存迷宫的字符数组
34 int vis[MAXN][MAXN]={0};    //到各个位置的最短距离设置初始化为INF
35 int N,M;    
36 typedef pair<int,int> P;    
37 int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};      //4个方向的移动向量
38 
39 bool in(int x,int y){                           //判断是否越界
40     return 0<=x&&x<N&&0<=y&&y<M;
41 }
42 //求从(sx,xy)到(gx,gy)的最短距离,无法到达就是INF
43 int bfs(){
44     queue<P> q;
45     q.push(P(sx,sy));   //将起点加入队列，并初始化距离为0
46     vis[sx][sy]=0;
47     while(q.size()){
48         P p=q.front();  //从队列取出第一个元素
49         q.pop();
50         if(p.first==gx&&p.second==gy) break;    //达到重点退出
51         for(int i=0;i<4;i++){
52             int dx=p.first+dir[i][0];
53             int dy=p.second+dir[i][1];
54             if(in(dx,dy)&&a[dx][dy]!='#'&&vis[dx][dy]==INF){
55                 q.push(P(dx,dy));
56                 vis[dx][dy]=vis[p.first][p.second]+1;
57             }
58         }
59     }
60     return vis[gx][gy];
61 }
62 void solve(){
63     int sum=bfs();
64     printf("%d",sum);
65 }
66 int main(){
67     cin>>N>>M;
68     for(int i=0;i<N;i++){
69         for(int j=0;j<M;j++){
70             cin>>a[i][j];
71             vis[i][j]=INF;
72             if(a[i][j]=='S'){
73                 sx=i;
74                 sy=j;
75             }
76             if(a[i][j]=='G'){
77                 gx=i;
78                 gy=j;
79             }
80         }
81     }
82     //scanf("%s",a);
83     solve();
84     return 0;
85 }