【31. 走迷宫（BFS）】

• 当要求最短路径时，并且边的权值为1时 使用BFS(广度优先搜索。)

思路

• 用 g[n][m] 存储地图，d[n][m] 存储起点到 n,m 的距离。
• 从起点开始广度优先遍历地图。
• 当地图遍历完，就求出了起点到各个点的距离，输出d[n][m]即可。

图讲解

使用队列的原因

• 因为当走到一个点后，有四种选择方向，必须同时向四个方向走，但是计算机一次性就只能执行一步，所以将待处理的方向依次放到队列中
• 每次走到相应点，就从队列中取出，看看是往哪个方向走

题目

方法1：模拟队列

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int, int> PII;
 const int N = 110;
 
 int n, m;
 int g[N][N];  //存放的是地图
 int d[N][N];  //存该点到起点的距离
 
 PII q[N * N]; //手写队列
 


int bfs()
 {
    int hh = 0, tt = 0;    //定义队头和队尾
    q[0] = {0, 0};          //进行初始化
    memset(d, -1, sizeof(d)); //距离初始化为- 1表示没有走过
    d[0][0] = 0;             //表示起点走过了
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //定义x方向的向量和y方向的向量

    while (hh <= tt)  //队列不为空
    {
    
      PII t = q[hh ++];  // 取出队头元素
        
        for (int i = 0; i < 4; i ++)     //枚举四个方向
        {
            int x = t.first + dx[i], y =t.second + dy[i];   ////x表示沿着此方向走会走到哪个点
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)//在边界内 并且是空地可以走 且之前没有走过
            
            {
                d[x][y] = d[t.first][t.second] + 1;  //到起点的距离
                q[ ++ tt] = {x, y};                 //新坐标入队
            }
            
        }
    }
    return d[n - 1][m - 1];     ////输出右下角点距起点的距离即可
    
    
 }
 

 
 int main()
 {
     cin >> n >> m;
     for (int i = 0; i < n; i ++)
     {
         for (int j = 0; j < m; j ++)
         {
            cin >> g[i][j];
         }
     }
     
     cout << bfs() << endl;
     return 0;
 }

方法2：STL

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 110;

typedef pair<int, int> PII;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue< pair<int, int> > q;

    q.push({0, 0});

    memset(d, -1, sizeof(d));

    d[0][0] = 0;


    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())//队列不为空
    {
        PII t = q.front();//取队头元素

        q.pop();//出队

        for (int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;//当前点到起点的距离
                q.push({x, y});//将新坐标入队
            }
        }
    }

    return d[n - 1][m -1];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

return d[n-1][m-1]是最小路径

• 第一次找到这个点的时候(即最短距离)这个点就被标记了 如果下次访问这个点就访问不到(所以不是找到了就跳出循环）
• 访问不到后，队列中的元素会为依次弹出，当队列为空时就退出循环。

打印路径

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
PII q[N*N],Prev[N][N];         //多开个数组，记录一下前面一个点是多少
int g[N][N], d[N][N];
int n, m;
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0};
    memset(d, -1, sizeof d);

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    d[0][0] = 0;
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        for(int i = 0; i < 4; i ++ )
        {
            int x = dx[i] + t.first, y = t.second + dy[i];

            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                Prev[x][y] = t;                   //将前面一个点存储起来
                q[++ tt] = {x, y};
            }
        }
    }
    int x = n - 1, y = m - 1;
    while(x || y)//有一个不d等于0
    {
        cout << x << ' ' << y << endl;          //打印目前点
        PII t = Prev[x][y];                    //寻找前面一个点，继续打印
        x = t.first, y = t.second;
    }

    return d[n - 1][m - 1];
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m;j ++)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}