BFS算法求迷宫的最短路径

        BFS(Breadth-First Search)算法的具体实现就是：通过不断取得某个状态能够达到的所有状态并将其加入队列尾， 并且由于队列本身的特性先加入队列的状态总是先得到处理，这样就可以总是先将需要转移次数更少的状态进行处理。换句话说就是总是取得了这个状态的树中更接近根部的节点，又或者是总是让搜索树的广度得到尽可能增加。拿一个例子来说，有一个如图所示的迷宫，'#' 为墙壁，'.' 为道路，'S' 为起点，'G' 为终点，需要我们找出从起点到达终点的最短路径。

10 10  //地图的长和宽
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

在这个问题中，找到从起点到终点的最短路径其实就是一个建立队列的过程：

1.从起点开始，将其加入队列，设置距离为0；

2.从队列首端取出位置，将从这个位置能够到达的位置加入队列，并且让这些位置的距离为上一个位置的距离加上1；

3.一轮探索至无法继续向队列中添加元素，即当前所在点的四周情况全部考虑完成后，循环第二步，直到将终点添加到队列中。说明此时已经找到了路径；

#include <cstdio>
#include <queue>
using namespace std;

const int INF = 100000000;
typedef pair<int, int> P;
char maze[101][101];
int n, m;
int sx, sy, gx, gy;
int d[101][101];
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(nx >= 0 && nx < n && ny >= 0 && 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];
}

int main()
{
    scanf("%d %d", &n, &m);
    getchar();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%c", &maze[i][j]);
        }
        getchar();
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maze[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            else if(maze[i][j] == 'G'){
                gx = i;
                gy = j;
            }
        }
    }
    printf("%d\n", BFS());
    return 0;
}

        这个过程中，每次处理的位置所对应的距离是严格递增的，即在数组 d[][] 中可以看到一条数值为1、2、3、4、5...的通路，因此一旦找到终点，当时的距离就是最短距离，该距离被记录在 d[gx][gy] 中。搜索可移动到的位置所使用的判断条件中不仅仅是不碰墙壁、不超过边界，还有一个就是没有到达过，体现在 d[nx][ny] 的数值没有被修改过，因为如果已经到达了这个位置，这说明已经有更短的路径到达这个位置，这次到达这个位置的路径是更差的，可以不予考虑了。

扩展一道 POJ-3984 迷宫问题

题目链接：https://cn.vjudge.net/problem/POJ-3984

分析：这道题因为需要输出最短路径的坐标信息，所以我使用了一个数组将路径上每个点的前一个点用数组保存了起来。

代码：

#include <cstdio>
#include <queue>
using namespace std;

const int INF = 100000;
typedef pair<int, int> P;
int maze[5][5], d[5][5];
P father[5][5];  //记录上一个节点信息
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  //四个方向

void BFS(){
    queue<P> que;
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            d[i][j] = INF;
            father[i][j].first = -1;
            father[i][j].second = -1;
        }
    }
    que.push(P(4, 4));
    d[4][4] = 0;
    while(que.size()){
        P p = que.front();
        que.pop();
        if(p.first == 0 && p.second == 0) break;
        for(int i = 0; i < 4; i++){
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && maze[nx][ny] != 1 && d[nx][ny] == INF){
                que.push(P(nx, ny));
                father[nx][ny].first = p.first;
                father[nx][ny].second = p.second;
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return;
}

int main()
{
    char c;
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            scanf("%d", &maze[i][j]);
    BFS();
    int i = 0, j = 0;
    while(i != -1 && j != -1){
        printf("(%d, %d)\n", i, j);
        int tmp = i;  //有坑，必须先保存了i的值再做修改
        i = father[i][j].first;
        j = father[tmp][j].second;
    }
    return 0;
}

上下左右四种情况的判断 用数组加一个for循环 可以说是很神奇了