题目: 给定一个大小为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\n", res);   }  };      int main(void)  {   Program P;   P.solve();      return 0;  }