迷宫的最短路径（宽度优先搜索）

题目

给定一个大小为$N|timesM$的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个的通道移动，请求出从起点到终点所需的最小步数。限制条件$N,M\le 100$。

输入

（’#‘,'.','S','G'分别表示墙壁、通道、起点和终点）

$N=10,M=12$
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出

22

分析

宽度优先搜索按照距开始状态由近即远的顺序进行搜索，因此可以很容易地用来求最短路径、最少操作之类问题的答案。

可以用d[N][M]数组把最短距离保存起来，用充分大得常数INF来初始化，这样一来，尚未到达的位置就是INF。

因为要向四个方向移动，用dx[4]和dy[4]两个数组来表示四个方向向量，通过循环就可以实现四个方向移动得遍历。

代码

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
#define MAX_SIZE 100
#define INF 100000000

struct Place{
    int x;
    int y;
};

char maze[MAX_SIZE][MAX_SIZE+1];
int d[MAX_SIZE][MAX_SIZE];

void bfs(Place s, Place g, int n, int m){
	// 四个移动方向，对应右、下、左、上
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    // 初始化距离数组，赋一个较大值INF
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            d[i][j] = INF;
    queue<Place> que;
    que.push(s);
    d[s.x][s.y] = 0;
    while(!que.empty()){
        Place p = que.front();
        que.pop();
        // 找到出口
        if(p.x == g.x && p.y == g.y)
            break;
        for(int i=0; i<4; i++){
            int nx = p.x + dx[i], ny = p.y + dy[i];
            if(0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != '#' && d[nx][ny] == INF){
                Place tmp;
                tmp.x = nx;
                tmp.y = ny;
                que.push(tmp);
                // 当前位置可走通，则距离加一
                d[nx][ny] = d[p.x][p.y] + 1;
            }
        }
    }
    //若输出INF则为死迷宫，反之，输出的是最短距离
    printf("%d\n", d[g.x][g.y]);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
        scanf("%s", maze[i]);
    Place s, g;
    // 查询迷宫开始和结束位置
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(maze[i][j] == 'S'){
                s.x = i;
                s.y = j;
            }
            if(maze[i][j] == 'G'){
                g.x = i;
                g.y = j;
            }
        }
    }
    // bfs遍历
    bfs(s, g, n, m);
    return 0;
}

输出