题解 | 迷宫寻路

#include <iostream>
#include <queue>
using namespace std;
/*
迷宫BFS思路模板：
queue<struct point> qu;
根节点入队
while (队列不为空)
{
   访问并保存队首元素
   如果队首元素满足条件，则返回相应的值（出口）
   访问该队首元素的子节点
   如果子节点存在且能够访问，则子节点入队
}
*/

struct point
{
    int x;
    int y;
    int step;//保存步数
};

//方位数组，便于寻找对应的子节点
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
char grid[105][105];//迷宫网格
bool visit[105][105] = {false};//记忆化搜索数组
queue<struct point> qu;

int bfs(struct point start,struct point end,int n,int m)
{
    qu.push(start);//start入队
    while (!qu.empty())
    {
        point check = qu.front();//访问队首元素
        qu.pop();
        if (check.x == n && check.y == m)//bfs函数的出口
        {
            return check.step;
        }
        for (int i = 0;i < 4;i++)//访问对应子节点
        {
            int nextx = check.x + dx[i];
            int nexty = check.y + dy[i];
            if (nextx >= 1 && nexty >= 1 && nextx <= n && nexty <= m && !visit[nextx][nexty] && grid[nextx][nexty] != '#')//保证子节点在网格中，且该子节点可访问
            {
                point temp;
                temp.x = nextx;
                temp.y = nexty;
                visit[temp.x][temp.y] = true;//标记子节点已访问，保证该节点不会重复访问
                temp.step = check.step + 1;//记录步数
                qu.push(temp);//子节点存在，则子节点入队
            }
        }
    }
    return -1;
}
int main() 
{
    int n,m;
    cin >> n >> m;
    //迷宫网格采用1-based索引
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            cin >> grid[i][j];//输入迷宫网格
        }
    }
    point start,end;
    start.x = 1;
    start.y = 1;
    start.step = 0;//初始化start的步数为0
    end.x = n;
    end.x = m;
    int ret = bfs(start,end,n,m);//用ret保存步数
    if (ret == -1)//步数为-1，则无法到达终点
    {
        cout << "No";
    }
    else 
    {
        cout << "Yes";
    }
    return 0;
}