题解：P1713 麦当劳叔叔的难题

· · 题解

题目传送门：

问题分析

这是一个关于在网格中寻找路径的问题，需要找到从左下角到右上角的最短路径和最长路径（每个格子只能经过一次），然后计算它们的时间差。

解决思路

最短路径：可以使用广度优先搜索（BFS）来找到，因为 BFS 保证找到的路径是最短的。 最长路径：这是一个 NP-Hard 问题，在本题中，我们可以通过分析发现，最长路径的长度等于网格总格子数减去障碍物数量再减 1。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <set>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // 障碍物的集合，用于快速判断某个格子是否是障碍物
    set<pair<int, int>> obstacles;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        obstacles.insert({x, y});
    }

    // 起点和终点
    pair<int, int> start = {1, 1};
    pair<int, int> end = {n, n};

    // 如果起点或终点是障碍物，直接输出0
    if (obstacles.count(start) || obstacles.count(end)) {
        cout << 0 << endl;
        return 0;
    }

    // BFS计算最短路径
    vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));
    queue<pair<pair<int, int>, int>> q;
    q.push({start, 0});
    visited[1][1] = true;
    int min_time = -1;

    // 四个方向：上、右、下、左
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    while (!q.empty()) {
        auto [pos, time] = q.front();
        q.pop();
        int x = pos.first;
        int y = pos.second;

        // 如果到达终点，记录最短时间并退出循环
        if (x == n && y == n) {
            min_time = time;
            break;
        }

        // 尝试四个方向
        for (auto [dx, dy] : directions) {
            int nx = x + dx;
            int ny = y + dy;

            // 检查是否越界、是否是障碍物、是否已访问
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && 
                !obstacles.count({nx, ny}) && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({{nx, ny}, time + 1});
            }
        }
    }

    // 计算最长路径
    int max_time = n * n - m - 1;

    // 输出结果
    cout << max_time - min_time << endl;

    return 0;
}

代码解释

输入处理：读取网格大小 n 和障碍物数量 m，然后将每个障碍物的坐标存入集合中。

起点和终点检查：如果起点或终点是障碍物，直接输出 0。

BFS 计算最短路径： 使用队列进行 BFS，每个元素包含当前位置和到达该位置的时间。

使用 visited 数组记录已经访问过的格子，避免重复访问。

四个方向分别是上、右、下、左，按顺序尝试每个方向。

当到达终点时，记录最短时间并退出循环。

计算最长路径：最长路径的长度等于总格子数减去障碍物数量再减 1。

输出结果：输出最长路径和最短路径的时间差。

时间复杂度：BFS 的时间复杂度是 O (n²)，因为每个格子最多被访问一次

空间复杂度：主要是 visited 数组和队列的空间，也是 O (n²)。

这个算法高效地解决了问题，通过 BFS 找到最短路径，并通过分析得出最长路径的长度。