广度优先搜索（BFS）——迷宫的最短路径

2023-01-06 11:37:12

宽度优先搜索按照距开始状态由近到远的顺序进行搜索，因此可以很容易的用来求最短路径,最少操作之类问题的答案。
宽度优先搜索介绍(一篇不错的文章)。

题目描述：

给定一个大小为N*M的迷宫。迷宫有通道和墙壁组成，每一步可以向邻接的上下左右的通道移动。请求出从起点到终点所需要的最小步数。
例如，N为10， M为10，输入的迷宫如下表示，其中S表示起点，G表示终点，"."表示通道，“#”表示墙壁

样例输入：

10 10

S######.

......#..#
.#.##.##.#
.#........

.##.

....#....#
.#######.#
....#.....
.####.###.
....#...G#

样例输出：

思路：

用到队列（queue），并且在本例中定义了新的数据类型P，while (que.size())真段代码是说，如果队列的长度为0.则终止循环，就像是排着个长队一样，
从队首开始，判断一个，取出，然后放入下一个，知道找到最终的。中间都去除了，距离为0
在这个问题中，找到从起点到终点的最短路径其实就是一个建立队列的过程：

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

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

3.循环2直到将终点添加到队列中，这说明我们已经找到了路径；

注意到在这个过程中，每次处理的位置所对应的距离是严格递增的，因此一旦找到终点，当时的距离就是最短距离；

同样基于这个原因，搜索可移动到的位置所使用的判断条件中不仅仅是不碰墙壁、不超过边界，还有一个就是没有到达过，因为如果已经到达了这个位置，这说明已经有更短的路径到达这个位置，这次到达这个位置的路径是更差的，不可能得到更好的最终解。

AC代码：


# include <iostream>
# include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 100;
const int INF = 1000000;//初始时用充分大的常数INF来初始化，这样尚未达到的位置就是INF，同时标记

typedef pair<int, int> P;
char maze[MAX_N][MAX_M+1];
int N, M;//行/列
int sx, sy;//起点的位置
int gx, gy;//终点的位置

int d[MAX_N][MAX_N];//储存起到某一点的距离
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0. - 1 };//表明每次x和y方向的位移
//分别是（1，0）（0，1）（-1，0）（0，-1）

void bfs()
 {
    queue<P> que;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
            d[i][j] = INF;//初始化所有点的距离为INF
    }
    que.push(P(sx, sy));//因为P是新定义的，可以直接把二维数组的下标放进去，和C语言的结构体类似
    d[sx][sy] = 0;//从起点出发将距离设置为 0，并放入队列首段

    while (que.size())//题目保证路有终点，直到队列的长度为0 为止
    {
        P p = que.front(); que.pop();
        int i;
        for (i = 0; i < 4; i++)
        {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];//因为p是新声明的数据类型P的一个子数据，P中有两个，一个是横坐标，一个是纵坐标
                                      //移动后的坐标
            //判断可移动且没到过
            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;
                if (nx == gx && ny == gy) break;
            }
        }
        if (i != 4) break;

    }
 }
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> maze[i];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            if (maze[i][j] == 'S')
            {
                sx = i; sy = j;
            }
            if (maze[i][j] == 'G')
            {
                gx = i; gy = j;
            }
        }
    bfs();
    cout << d[gx][gy] << endl;

    return 0;
}

码农公寓