D. Drunken Maze - 题解

比赛与标签

比赛: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) 标签: brute force, dfs and similar, graphs, shortest paths 难度: *1700

喵~ 题目到底在说什么呀？

主人Sama，你好喵~！今天我们来解决一个超级有趣的迷宫问题呐！(ฅ'ω'ฅ)

想象一下，我们正身处一个 n x m 大小的迷宫里，迷宫里有平地 .，有墙壁 #，还有一个起点 S 和一个终点 T。我们的任务就是找到从 S 到 T 的最短路径，也就是步数最少的走法。

但是！这里有一个非常可爱的设定喵~ 如果我们像一只喝醉酒的小猫一样，连续朝着同一个方向（上、下、左、右）走超过三步，我们就会失去平衡摔倒，这是不允许的！也就是说，我们朝一个方向最多只能连续走三步。走三步之后，下一步必须换个方向才行。

比如说，右->右->右 是可以的，但是 右->右->右->右 就不行啦！不过 右->右->右 之后，我们可以先往 左 走一步，再继续往 右 走，这样是可以的哦。

我们的目标就是，在遵守这个“防摔倒”规则的前提下，找到从 S 到 T 的最少步数。如果到不了，就告诉人家一声 -1 啦~

怎样才能不晕乎乎地走出迷宫呢？

一看到“最短路径”，我们聪明的脑袋里是不是立刻就浮现出了 广度优先搜索（BFS） 的身影呢？喵~ BFS简直就是为在无权图中找最短路而生的！

但是，一个普通的BFS只记录 (行, 列) 位置是不够的。为什么呢？因为它无法知道我们是怎么到达当前位置的。我们是刚换了方向，还是已经连续走了三步了？这些信息会直接影响我们下一步能怎么走。

所以，我们需要一个更强大的BFS！我们需要在状态里加入更多的信息，来记住我们“醉酒”的程度，也就是连续朝一个方向走了多少步，的说。

一个完美的状态应该包含这些信息： 状态 = (当前行 r, 当前列 c, 上一步的方向 dir, 在这个方向上连续走的步数 cnt)

• (r, c): 我们现在在迷宫的哪个格子上。
• dir: 我们上一步是朝哪个方向走的？我们可以用 0, 1, 2, 3 来代表上、右、下、左。对于起点 S，因为它还没有移动，我们可以用一个特殊值（比如-1）来表示。
• cnt: 我们已经连续朝 dir 方向走了多少步了。这个值只可能是 1, 2, 或 3。

有了这个增强版的状态，我们的BFS就可以这样工作啦：

1. 定义状态空间: 一个点 (r, c) 不再是一个节点，而是多个。具体有多少个呢？

   • 一个初始状态（在起点S，还没开始走）。
   • 对于每个方向（4个），都有可能连续走了1步、2步、3步。所以是 4 * 3 = 12 种“移动中”的状态。
   • 总共 1 + 12 = 13 种关于“怎么走”的状态。 所以，我们的图实际上有 n * m * 13 个节点！每个节点代表 (位置, 移动状态)。

2. BFS流程:

   • 创建一个队列，用来存放我们的增强版状态 (r, c, dir, cnt)。
   • 创建一个 dist 数组，dist[r][c][移动状态] 用来记录到达这个完整状态所需的最短步数，同时也能判断一个状态是否被访问过。为了方便，我们可以把三维的 dist 数组拍平成一维的，大小就是 n * m * 13。
   • 把初始状态 (起点行, 起点列, -1, 0) 和距离 0 加入队列和dist数组。
   • 当队列不为空时，取出队首状态 (r, c, dir, cnt)。
   • 尝试向四个新方向 new_dir 移动到 (nr, nc)。
     • 首先，(nr, nc) 不能是墙，也不能越界。
     • 计算新的连续步数 new_cnt：
       • 如果 new_dir == dir，说明我们继续朝老方向走，new_cnt = cnt + 1。
       • 如果 new_dir != dir，说明我们换方向了，new_cnt 重置为 1。
     • 规则检查！ 如果 new_cnt > 3，这个走法是犯规的，直接跳过！
     • 如果新的状态 (nr, nc, new_dir, new_cnt) 还没有被访问过（通过检查dist数组），我们就更新它的距离 dist[新状态] = dist[旧状态] + 1，并把它推入队列。

3. 终点判断: 当我们在BFS过程中，第一次到达某个状态，其位置 (r, c) 恰好是终点 T 的位置时，因为BFS的特性，我们找到的步数一定是最短的！直接输出这个步数，任务就完成啦，喵~

4. 无解情况: 如果队列都空了，我们还没能到达终点 T，那就说明 T 是一个遥不可及的梦乡，我们到不了啦，输出 -1 就好。

这个方法把一个复杂的约束问题，转化成了一个在更大状态图上的标准最短路问题，是不是很巧妙呀？(>^ω^<)

奉上可以AC的代码喵~

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int main() {
    // 使用C++标准IO加速，让程序跑得像小猫一样快~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    // cin.ignore() 用来吃掉 cin >> m 后面的换行符，防止 getline 读到空行
    cin.ignore();

    vector<string> grid;
    string line;
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        grid.push_back(line);
    }

    // 找到起点S和终点T的位置
    int sr = -1, sc = -1, tr = -1, tc = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') {
                sr = i;
                sc = j;
            } else if (grid[i][j] == 'T') {
                tr = i;
                tc = j;
            }
        }
    }

    // 方向数组，0:上, 1:右, 2:下, 3:左
    vector<int> dr = {-1, 0, 1, 0};
    vector<int> dc = {0, 1, 0, -1};

    // dist数组，大小为 n * m * 13。13代表了1个初始状态 + 4个方向 * 3种连续步数
    // 初始化为-1，表示所有状态都未到达
    vector<int> dist(n * m * 13, -1);
    // 队列存储状态元组: {行, 列, 上一步方向, 连续步数}
    queue<tuple<int, int, int, int>> q;

    // 起始状态的索引。初始状态我们定义为 state_index = 0
    int start_index = (sr * m + sc) * 13 + 0;
    dist[start_index] = 0;
    // 将起点入队，方向为-1（特殊值），连续步数为0
    q.push(make_tuple(sr, sc, -1, 0));

    while (!q.empty()) {
        // 取出队首状态
        auto [r, c, d, cnt] = q.front();
        q.pop();

        // 计算当前状态的一维索引
        // d == -1 是初始状态，索引为0
        // 其他状态的索引计算: 1 (跳过初始状态) + 方向*3 + (连续步数-1)
        int state_index = (d == -1) ? 0 : (1 + d * 3 + (cnt - 1));
        int linear_index = (r * m + c) * 13 + state_index;

        // 如果当前位置是终点T，我们成功啦！直接输出距离
        if (r == tr && c == tc) {
            cout << dist[linear_index] << '\n';
            return 0;
        }

        // 尝试向四个方向移动
        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            
            // 检查边界和墙壁
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc] == '#') continue;

            int new_count;
            if (d == dir) { // 如果方向相同
                new_count = cnt + 1;
                if (new_count > 3) continue; // 连续超过3步，犯规！
            } else { // 如果换了方向
                new_count = 1; // 连续步数重置为1
            }

            // 计算新状态的一维索引
            int new_state_index = 1 + dir * 3 + (new_count - 1);
            int new_linear_index = (nr * m + nc) * 13 + new_state_index;

            // 如果新状态还没被访问过
            if (dist[new_linear_index] == -1) {
                // 更新距离并入队
                dist[new_linear_index] = dist[linear_index] + 1;
                q.push(make_tuple(nr, nc, dir, new_count));
            }
        }
    }

    // 队列空了还没到终点，说明无解
    cout << -1 << '\n';
    return 0;
}

我们的猫步有多快呀？——复杂度分析

• 时间复杂度: O(N * M) 的说 我们的状态总数是 N * M * 13。对于BFS来说，每个状态最多只会被访问一次。从每个状态出发，我们最多会尝试4个方向的移动。所以总的操作次数大约是 N * M * 13 * 4。因为13和4都是常数，所以时间复杂度就是 O(N * M) 啦，非常高效！

• 空间复杂度: O(N * M) 的说 我们主要的内存开销是 dist 数组和队列 q。dist 数组的大小是 N * M * 13，队列在最坏情况下也可能存下这么多状态。所以空间复杂度也是 O(N * M) 的。

喵呜~ 知识点总结时间！

这道题真是太棒了，让我们学到了好多东西呐！

1. BFS的灵活应用: 这不是一道裸的BFS，而是一道经典的 BFS变种题。它告诉我们，当问题有额外限制时，不要害怕，试着把限制条件融入到状态定义中去！

2. 状态设计是关键: 解题的核心在于如何设计BFS的状态。将 (行, 列) 扩展为 (行, 列, 方向, 连续步数)，是把复杂约束转化为图论模型的关键一步。这个思想在很多动态规划和搜索问题中都非常有用哦。

3. 空间换时间: 我们用了一个比迷宫大小大13倍的 dist 数组来记录所有可能状态的距离。这就是典型的“空间换时间”思想，通过记录更详细的信息来避免重复搜索，从而保证了算法的效率和正确性。

4. 状态压缩/映射: 把 (r, c, dir, cnt) 这样一个多维状态，通过 (r * m + c) * 13 + state_index 的方式映射到一个一维数组的下标上，是一种非常实用的编程技巧，能让代码更简洁，也方便我们管理 dist 和 visited 数组。

希望这篇题解能帮到主人Sama，喵~ 下次再遇到这种带限制的最短路问题，你一定也能像聪明的猫娘一样，轻松找到最优解的！加油哦！(๑•̀ㅂ•́)و✧