知识点：

DPS是按照一条路走到底，所以一定会找到一个解；BFS是一层一层走的，每层找到的路径长度都一样，所以能找到最优解，相较于DFS搜索时间更少，效率高。

DP是个特殊的最短路问题，是没有环的最短路问题。只有当每条路径的权重为1时，才能使用BFS来解最短路问题，否则需要特定的最短路算法来解决。注：BFS时间复杂度会比最短路算法的时间复杂度低。

ACwing 844. 走迷宫

题目链接：https://www.acwing.com/problem/content/846/
主要思路如下图，最后输出右下角坐标到起点的距离即可：

实现思路：
我么使用一个队列存储可能的路径(x,y)，每次拿队头的元素判断下一步可以走的位置，如果可以走且之前没有走过，那么将该坐标放入队尾。当队列不为空就说明有位置可以走，就一直走下去，当所有位置都走完时，右下角的距离就是最短路径。

这个队列中的元素是个坐标，所以可以用pair类型存储，同时队列的实现可以通过数组+头尾指针实现：队头用hh标记，队尾用tt标记，开始都初始化为0，拿出队头元素t：PII t = q[hh++]（先拿出来队头hh再++），当对头的下一个位置满足条件时，将其放入队尾q[++tt]={x,y};（队尾先++再赋值）

在判断以下一个位置能不能走时有个判断技巧，简化了四个方向的判断，具体如下：

手写队列(数组)实现

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

const int N = 110;
typedef pair<int,int> PII;//记录可能的路径，每个元素为(x,y)

int n,m;
int g[N][N];//记录图
int d[N][N];//记录各点到起点的距离
PII q[N*N];//队列记录路径

int bfs(){
    int hh=0,tt=0;//队头队尾的位置
    memset(d,-1,sizeof(d));//初始化距离为-1
    d[0][0]=0;
    q[0]={0,0};
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//变化向量
    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];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
            {
                q[++tt]={x,y};//当(x,y)位置满足条件可以作为下一步的候选项放入队列
                d[x][y]=d[t.first][t.second]+1;//距离起点距离为上一距离+1
            }
        }
    }
    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;
}

C++队列实现：

代码：

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

const int N = 110;
typedef pair<int,int> PII;//记录可能的路径，每个元素为(x,y)

int n,m;
int g[N][N];//记录图
int d[N][N];//记录各点到起点的距离
queue<pair<int,int>> q;//队列记录路径

int bfs(){
    memset(d,-1,sizeof(d));//初始化距离为-1
    d[0][0]=0;
    q.push({0,0});
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//变化向量
    while(q.size())//队列不为空，表示有下一步
    {
        auto 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)
            {
                q.push({x,y});//当(x,y)位置满足条件可以作为下一步的候选项放入队列
                d[x][y]=d[t.first][t.second]+1;//距离起点距离为上一距离+1
            }
        }
    }
    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;
}