麦当劳叔叔的难题

信息

此题目来自洛谷，原始题目与提交代码请前往 P1713 麦当劳叔叔的难题 - 洛谷。

注意

这道题目有误，当前呈现的题目是已经修正过的版本。修正内容已用 ~~删除线~~ 强调。

题目描述

话说我们铭铭小朋友成功的回答了爸爸的问题，自然少不了要去索要些奖励，抠门的爸爸一看报纸，嘿，门口的麦当劳在搞活动，还有免费午餐哦，不过前提条件：得正确回答麦当劳叔叔的问题。

问题是这样描述的：

“我面前有很多个小朋友，我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的，我希望你帮我找出最聪明和最不聪明的小朋友，可能的最大的到达时间差。但是，小朋友只能按照一个特殊的规则前进。小朋友面前有一个 ${n}\times{n}$ 的格子矩阵，~~左下角~~右下角的格子是起点，~~右上角~~左上角的格子是大门。每个孩子每秒可以走向上、下、左、右前进一个格子，每个格子只能经过一次。但矩阵中间有一些障碍区，不能通过，只能绕过。”

例如， ${4}\times{4}$ 的矩阵，格子 $(1,1),(2,3),(4,2)$ 为障碍区，黑格子就是一条可行的路线。时间为 $7$ 。

输入格式

第一行为两个整数 $n,m$ 。

第二至第 $m+1$ 行里，每行描述一个障碍区。用两个整数表示 $x,y$ 。

输出格式

仅一行，那个最大的时间差。

输入输出样例

输入 #1

输出 #1

说明/提示

${2}\le{n}\le{10}$ ， ${0}\le{m}\le{100}$ ， ${1}\le{x},{y}\le{n}$ 。

题目解答

注意

本题题解尚未完成/尚未完善，不足以 AC 通过评判。

本来有个基于 A* 算法的题解的，要不是题目有误，老是 WA ，所以我给它删了。

深度优先搜索

很容易想到，这道题我们可以使用深度优先搜索 (DFS) 来解决。

我们先来定义：

#include <iostream>
#include <vector>
#define repeat(n) for (size_t _ = 0; _ < n; _++)
typedef unsigned short u_short;
using namespace std;

u_short n, m;
u_short minTime = 65535;
u_short maxTime = 0;
vector<pair<short, short>> directions = {pair(0, 1), pair(0, -1), pair(1, 0), pair(-1, 0)};

int main() {
    cin >> n >> m;
    vector<vector<bool>> borders(n, vector<bool>(n, false));
    repeat (m) {
        u_short x, y;
        cin >> x >> y;
        borders[x - 1][y - 1] = true;
    }
    
    cout << maxTime - minTime << endl;

    return 0;
}

这些都是题目中有所说明的。我们来实现 DFS 方法：

void dfs(u_short x, u_short y, u_short time, vector<vector<bool>>& visited) {
    //if (x == n - 1 && y == n - 1) {
    if (x == 0 && y == n - 1) {
        minTime = min(time, minTime);
        maxTime = max(time, maxTime);
        return;
    }
    for (auto direction : directions) {
        u_short nx = x + direction.first, ny = y + direction.second;
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
            visited[nx][ny] = true;
            dfs(nx, ny, time + 1, visited);
            visited[nx][ny] = false;
        }
    }
}

之后，我们修改主方法：

int main() {
    /* 省略部分代码 */
    
    borders[0][0] = true;
    //dfs(0, 0, 0, borders);
    dfs(n - 1, 0, 0, borders);
    borders[0][0] = false;
    cout << maxTime - minTime << endl;

    /* 省略部分代码 */
}

不出意料，这种方法成功 TLE 了。下面是完整代码：

/**
 * 洛谷 P1713 解答程序。
 * 基于 DFS 算法。
 * @author CoolCLK
 */
#include <iostream>
#include <vector>
#define U_SHORT_MAX 65535
#define repeat(n) for (size_t _= 0; _ < n; _++)
typedef unsigned short u_short;
using namespace std;

u_short n, m;
u_short minTime = U_SHORT_MAX;
u_short maxTime = 0;
vector<pair<short, short>> directions = {pair(0, 1), pair(0, -1), pair(1, 0), pair(-1, 0)};

void dfs(u_short x, u_short y, u_short time, vector<vector<bool>>& visited) {
    if (x == 0 && y == n - 1) {
        minTime = min(time, minTime);
        maxTime = max(time, maxTime);
        return;
    }
    for (auto direction : directions) {
        u_short nx = x + direction.first, ny = y + direction.second;
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
            visited[nx][ny] = true;
            dfs(nx, ny, time + 1, visited);
            visited[nx][ny] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    vector<vector<bool>> borders(n, vector<bool>(n, false));
    repeat (m) {
        u_short x, y;
        cin >> x >> y;
        borders[x - 1][y - 1] = true;
    }

    borders[0][0] = true;
    dfs(n - 1, 0, 0, borders);
    borders[0][0] = false;
    cout << maxTime - minTime << endl;

    return 0;
}

题目描述​

输入格式​

输出格式​

输入输出样例​

说明/提示​

题目解答​