题解 | #走迷宫#

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


bool CanWalk(int x, int y, vector<vector<char>> &maze)
{
    if (0 <= x && x <= maze[0].size() - 1 && 0 <= y && y <= maze.size() - 1 && maze[y][x] == '.')
    {
        maze[y][x] = '#'; // 若可以走则标记为走过
        return true;
    }
    return false;
}

void WalkMaze(int startX, int startY, int endX, int endY, vector<vector<char>> maze)
{
    bool hadFind = false;
    int step = 0;

    vector<pair<int, int>> site_list; // 至少需要走step步才能到达的位置坐标列表
    if (CanWalk(startX - 1, startY - 1, maze)) site_list.emplace_back(startX - 1, startY - 1);

    while (!hadFind && !site_list.empty())
    {
        vector<pair<int, int>> newSite_list; // 至少需要step+1步才能到达的位置坐标列表
        for (const pair<int, int> &site: site_list)
        {
            int x = site.first, y = site.second;
            // 判断是否为终点
            if (x == endX - 1 && y == endY - 1)
            {
                hadFind = true;
                break;
            }

            if (CanWalk(x - 1, y, maze)) newSite_list.emplace_back(x - 1, y);
            if (CanWalk(x + 1, y, maze)) newSite_list.emplace_back(x + 1, y);
            if (CanWalk(x, y - 1, maze)) newSite_list.emplace_back(x, y - 1);
            if (CanWalk(x, y + 1, maze)) newSite_list.emplace_back(x, y + 1);
        }

        site_list = newSite_list;
        if (!hadFind) ++step;
    }

    if (hadFind) cout << step;
    else cout << -1; // -1代表无法到达
    // cout << '\n';
}

int main()
{
    /// 处理数据输入
    int n, m; // n行m列的网格
    cin >> n >> m;

    int startX, startY; // 起点坐标
    int endX, endY;     // 终点坐标
    // 题目中的坐标(X, Y)表示迷宫网格中第X行第Y列的格子，与本人习惯相反，若要与题目一致，重命名即可。
    cin >> startY >> startX >> endY >> endX;

    vector<vector<char>> maze(n, vector<char>(m)); // 表示迷宫
    for (int y = 0; y < n; ++y)
        for (int x = 0; x < m; ++x)
            cin >> maze[y][x];

    /// 处理数据
    WalkMaze(startX, startY, endX, endY, maze);
}