题解 | #走迷宫#

#include <bits/stdc++.h> // 引入标准库头文件
using namespace std;

char ditu[1010][1010]; // 定义全局二维字符数组，表示地图
int n, m; // 定义全局变量，表示地图的行数和列数

// 定义广度优先搜索函数，参数为起点和终点坐标
int bfs(pair<int, int> b, pair<int, int> e) {
    queue<pair<int, int>> q; // 创建队列存储待访问的节点
    q.push(b); // 将起点加入队列
    ditu[b.first][b.second] = '*'; // 标记起点已访问
    int res = 0; // 初始化移动步数
    while (!q.empty()) // 当队列不为空时循环
    { 
        int size = q.size(); // 获取当前层的节点数
        while (size--) // 遍历当前层的所有节点,也因此保证了计数器res++的正确性
        { 
            pair<int, int> t = q.front(); // 获取队首节点
            q.pop(); // 弹出队首节点
            if (t == e) 
			  return res; // 如果当前节点为终点，返回移动步数
            else 
			{
                int dx[] = {-1, 0, 1, 0}; // 定义x方向的四个相邻节点偏移量
                int dy[] = {0, 1, 0, -1}; // 定义y方向的四个相邻节点偏移量
                for (int i = 0; i < 4; i++) { // 遍历四个方向
                    int nx = t.first + dx[i]; // 计算相邻节点的横坐标
                    int ny = t.second + dy[i]; // 计算相邻节点的纵坐标
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
                            ditu[nx][ny] == '.') { // 如果相邻节点合法且未被访问
                        q.push({nx, ny}); // 将相邻节点加入队列
                        ditu[nx][ny] = '*'; // 标记相邻节点已访问
                    }
                }
            }
        }
        res++; // 移动步数加一
    }
    return -1; // 若无法到达终点，返回-1
}

int main() {
    cin >> n >> m; // 输入地图的行数和列数
    int xs, ys, xt, yt; // 定义起点和终点的坐标
    cin >> xs >> ys >> xt >> yt; // 输入起点和终点的坐标
    for (int i = 1; i <= n; i++) // 遍历地图的每一行
        for (int j = 1; j <= m; j++) // 遍历地图的每一列
            cin >> ditu[i][j]; // 输入地图信息
    pair<int, int> be = {xs, ys}, en = {xt, yt}; // 定义起点和终点的坐标对
    int result = bfs(be, en); // 调用广度优先搜索函数，计算最短路径
    cout << result; // 输出结果
    return 0; // 程序正常结束
}