題目: 給定一個大小為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;
}
</strong></pre>