题目描述

走迷宫（BFS）宽度优先搜索

最短路算法

按每层搜索，（横着搜索）

C++ 代码

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

typedef pair<int, int> PII;  //pair 默认对first升序，当first相同时对second升序；

const int N = 110;

int n, m;
int g[N][N];   //存储的是图
int d[N][N];   //存储的是距离
PII q[N*N];    //定义一个手写队列

int bfs()
{
    int hh = 0;   //队头
    int 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)        //队列不空
    {
        auto t = q[hh++];     //取出队头

        for (int i = 0; i < 4; i++)      //枚举四个方向
        {
            int x = t.first + dx[i], y = t.second + dy[i];    //表示x、y方向能走到哪里
            //若要走的点在边界之内且为0（有空地，可以走），并且没有走过（距离为-1）
            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];              //c存入地图

    cout << bfs() << endl;

    return 0;
}