走迷宫（BFS + 队列）

基本思路

从起点开始走，走一步能抵达的点放进队列里，将这些点作为走第二步的起点，依此类推，直到第一次走到终点就终止，此时已经找到了从起点到终点的最短路径。

步骤

（1）先将起点初始化， 并放入队列

（2）用 while 循环在队列非空时，遍历队列里的点。遍历点的具体操作是：考虑队首元素能走到的点，将能走到的点放入队列中后，弹出队首元素，然后继续考虑新的队首元素能走到的点。

（3）如果队首元素的横纵坐标等于终点，则 return 步数。

?

下面推荐一个视频帮助理解

BFS广搜解决迷宫问题_哔哩哔哩_bilibili?

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

struct point
{
    int x;
    int y;
    int dis;
    point(int x1, int y1, int d)
    {
    	x = x1;
    	y = y1;
    	dis = d;
	} 
};
queue<point> dl; // point类型的队列

const int N = 110;
int n,m;
int map[N][N]; // 存入地图
bool v[N][N]; // 标记是否访问过

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

int bfs()
{
    point p1(0,0,0); // 将起点处初始化，并入队
    dl.push(p1);
    v[0][0] = true;
    
    while(!dl.empty())
    {
    	int x = dl.front().x, y = dl.front().y, step = dl.front().dis;
    	if(x == m-1 && y == n-1)
    	return step;
		for(int i=0;i<4;++i)
    	{
    		int x1 = x + dx[i];
    		int y1 = y + dy[i];
    		// 如果目的地没有障碍物、没有访问过、没有超出迷宫，才能继续下一步操作
    		if(map[y1][x1] == 0 && !v[y1][x1] && x1 < m && x1 >= 0 && y1 < n && y1 >= 0)
    		// 注意这里是用y来表示第几行，用x来表示第几列，因此是map[y1][x1]
    		{
    		    // 如果能抵达某个点，那个点就能作为走下一步的起点，因此放进队列里
    			point temp(x1, y1, 1+step);
    			v[y1][x1] = true; 
    			dl.push(temp);
			}
		}
		// 遍历了四个方向之后，此时队首已经无处可去，直接将其弹出队列，
		// 这样才能循环遍历队列里的各个元素
		dl.pop();
	}
	return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;++j)
            scanf("%d", &map[i][j]);
            
    printf("%d",bfs());
    
    return 0;
}