首页 / 软件开发 / 数据结构与算法 / 迷宫的最短路径算法 代码（C++）

迷宫的最短路径算法 代码（C++）2015-10-28题目: 给定一个大小为N*M的迷宫. 迷宫由通道和墙壁组成, 每一步可以向邻接的上下左右四格的通道移动.

请求出从起点到终点所需的最小步数. 请注意, 本题假定从起点一定可以移动到终点.

使用宽度优先搜索算法（DFS）, 依次遍历迷宫的四个方向, 当有可以走且未走过的方向时, 移动并且步数加一.

时间复杂度取决于迷宫的状态数, O（4*M*N）=O（M*N）.

代码:

/** main.cpp**Created on: 2014.7.17* *Author: spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#include <limits.h>#include <utility>#include <queue>using namespace std;class Program {static const int MAX_N=20, MAX_M=20;const int INF = INT_MAX>>2;typedef pair<int, int> P;char maze[MAX_N][MAX_M+1] = {"#S######.#","......#..#",".#.##.##.#",".#........","##.##.####","....#....#",".#######.#","....#.....",".####.###.","....#...G#"};int N = 10, M = 10;int sx=0, sy=1; //起点坐标int gx=9, gy=8; //重点坐标int d[MAX_N][MAX_M];int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; //四个方向移动的坐标int bfs（） {queue<P> que;for （int i=0; i<N; ++i）for （int j=0; j<M; ++j）d[i][j] = INF;que.push（P（sx, sy））;d[sx][sy] = 0;while （que.size（）） {P p = que.front（）; que.pop（）;if （p.first == gx && p.second == gy） break;for （int i=0; i<4; i++） {int nx = p.first + dx[i], ny = p.second + dy[i];if （0<=nx&&nx<N&&0<=ny&&ny<M&&maze[nx][ny]！="#"&&d[nx][ny]==INF） {que.push（P（nx,ny））;d[nx][ny]=d[p.first][p.second]+1;}}}return d[gx][gy];}public:void solve（） {int res = bfs（）;printf（"result = %d
", res）;}};int main（void）{Program P;P.solve（）;return 0;}

输出:

result = 22

作者：csdn博客 Mystra