BFS_Maze_求解迷宫最短路径

  1 /*
  2 10 10
  3 #.######.#
  4 ......#..#
  5 .#.##.##.#
  6 .#........
  7 ##.##.####
  8 ....#....#
  9 .#######.#
 10 ....#.....
 11 .####.###.
 12 ....#....#
 13 0 1
 14 9 8
 15 */
 16 #define _CRT_SECURE_NO_WARNINGS
 17 /*
 18 10 10
 19 #.######.#
 20 ......#..#
 21 .#.##.##.#
 22 .#........
 23 ##.##.####
 24 ....#....#
 25 .#######.#
 26 ....#.....
 27 .####.###.
 28 ....#....#
 29 0 1
 30 9 8
 31 */
 32 #include <iostream>
 33 #include <utility>
 34 #include <queue>
 35 using namespace std;
 36 
 37 const int INF = 100000000;
 38 const int MAX_N = 50, MAX_M = 50;
 39 
 40 typedef pair<int, int> P;
 41 //输入
 42 char maze[MAX_N][MAX_M];
 43 int N, M;
 44 int sx, sy;
 45 int gx, gy;
 46 //到各个位置最短距离的数组
 47 int d[MAX_N][MAX_M];
 48 
 49 //4个方向移动的向量--下，右，上，左
 50 int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
 51 
 52 //从(sx, sy) 到 (gx, gy)的最短距离
 53 int bfs()
 54 {
 55     queue<P> que;
 56     for (int i = 0; i < N; i++)                   //未走过的都为INF 
 57     for (int j = 0; j < M; j++) d[i][j] = INF;
 58     //将起点加入队列, 并把这一地点的距离设置为0
 59     que.push(P(sx, sy));
 60     d[sx][sy] = 0;
 61 
 62     //不断循环直到队列为空,长度为0
 63     while (que.size()) {
 64         //出队
 65         P p = que.front(); que.pop();
 66         //如果取出的状态已经是终点，则结束搜索
 67         if (p.first == gx && p.second == gy) break;
 68 
 69         //四个方向的循环
 70         for (int i = 0; i < 4; i++) {
 71             //移动之后的位置为 (nx, ny)
 72             int nx = p.first + dx[i], ny = p.second + dy[i];  //当前位置+方向 
 73 
 74             //判断是否可以移动以及是否已经访问过 (d[nx][ny] != INF 则已经访问过)
 75             if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {
 76                 que.push(P(nx, ny));          //将没有走过的路，入队
 77                 //可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离+1 
 78                 d[nx][ny] = d[p.first][p.second] + 1;
 79             }
 80         }
 81     }
 82     return d[gx][gy];
 83 }
 84 
 85 void solve()
 86 {
 87     int res = bfs();
 88     printf("%d
", res);
 89 }
 90 
 91 void Input()
 92 {
 93     cout << "设置Maze大小: 
";
 94     cin >> N >> M;
 95     cout << "设置迷宫(通路为 '.', 墙为'#'):
";
 96     for (int i = 0; i < N; i++) {
 97         for (int j = 0; j < M; j++)
 98             cin >> maze[i][j];
 99     }
100     cout << "设置入口: (sx, sy): ";
101     cin >> sx >> sy;
102     cout << "设置出口: (gx, gy): ";
103     cin >> gx >> gy;
104 }
105 
106 int main(int argc, char const *argv[])
107 {
108     Input();
109     solve();
110     return 0;
111 }