Moe's CF Life

哈喽，各位小伙伴们，喵~ 这里是你们的猫娘小助手！今天我们要一起解决一个关于爱与勇气（还有鳄鱼！）的有趣问题：D. Test of Love。ErnKor 为了心上人要渡过一条危险的河，我们当然要帮他规划出最安全的路线啦！

下面就让本喵带大家一步步分析这个问题，找到通往爱之彼岸的道路吧，喵~

题目大意

简单来说，我们要帮助 ErnKor 从河的左岸（位置 0）到达右岸（位置 n+1）。这条河的长度是 n 米。

河里有三种东西：

L：安全的木头 (Log)，可以站在上面。
W：冰冷的水 (Water)，在水里游泳会消耗体力。
C：可怕的鳄鱼 (Crocodile)，绝对不能踏入有鳄鱼的地方。

ErnKor 的行动规则如下：

在岸上或木头上时：他可以向前跳跃 1 到 m 米远的距离，可以跳到木头上，也可以跳进水里。
在水里时：他只能向前游 1 米，到达下一个位置。
体力限制：ErnKor 在整个渡河过程中，在水里游泳的总距离不能超过 k 米。

我们的任务就是判断，ErnKor 能不能在满足所有条件的情况下，成功从左岸（位置 0）到达右岸（位置 n+1）。

解题思路

一看到这种“能否到达终点”并且带有“最小代价”感觉的问题，猫猫的直觉就告诉我，这一定是个图论搜索问题，喵！我们要找的，其实就是一条从起点到终点的，游泳距离之和最小的路径。

那这个图的“点”和“边”是什么呢？

状态（图中的点）

一个简单的位置 i 不足以描述 ErnKor 的状态。因为他在位置 i 时，是在木头上还是在水里，这两种情况的后续行动是完全不同的。所以，一个完整的状态应该是 (当前位置, 所在介质)。

介质 0：在表面上（岸边或木头 L）
介质 1：在水里（W）

转移（图中的边）

状态之间的转移就代表了 ErnKor 的一次行动，而行动的“代价”就是游泳的距离。

从 (u, 表面) 跳跃：可以跳到 v = u+j (其中 1 <= j <= m)。
- 如果 v 处是木头 L，就转移到 (v, 表面) 状态。
- 如果 v 处是水 W，就转移到 (v, 水里) 状态。
- 这两种跳跃本身不消耗游泳体力，所以边权是 0。
从 (u, 水里) 游泳：只能游到 v = u+1。
- 如果 v 处是木头 L，就转移到 (v, 表面) 状态。
- 如果 v 处是水 W，就转移到 (v, 水里) 状态。
- 游泳需要消耗 1 米的体力，所以边权是 1。

呀！这不就是典型的边权只为 0 和 1 的最短路问题嘛？对于这种特殊的问题，我们有一个超级棒的算法——0-1 BFS！它比 Dijkstra 算法更简单也更快哦。

0-1 BFS 的核心思想：我们使用一个双端队列（deque）来代替普通 BFS 的队列。

当遇到一条权重为 0 的边时，我们将新节点加入到队头。
当遇到一条权重为 1 的边时，我们将新节点加入到队尾。

这样就能保证队列中的节点始终是按照路径代价（这里是游泳距离）从小到大排列的，完美地解决了我们的问题！

题解代码与分析

下面是具体的实现步骤，让我们一起看看代码是如何把思路变成现实的吧~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>

const int INF = 1e9 + 7;

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::string s;
    std::cin >> s;

    // 为了方便处理，我们在河的两边都加上岸，当作特殊的木头'L'，喵~
    // 位置 0: 左岸
    // 位置 1 到 n: 河流
    // 位置 n+1: 右岸
    std::string s_aug = "L" + s + "L";
    int len = n + 2;

    // dist[i][0]: 到达位置i的表面(木头/岸)的最小游泳距离
    // dist[i][1]: 到达位置i的水里的最小游泳距离
    std::vector<std::vector<int>> dist(len, std::vector<int>(2, INF));
        
    // 0-1 BFS 使用的双端队列
    std::deque<std::pair<int, int>> q;

    // 从左岸(位置0)开始，它是一个表面，游泳距离为0
    dist[0][0] = 0;
    q.push_front({0, 0}); // {位置, 介质类型}, 0代表表面, 1代表水里

    while (!q.empty()) {
        auto [u, type] = q.front();
        q.pop_front();

        int current_cost = dist[u][type];

        if (type == 0) { // 在表面上 (木头或岸)
            // 可以向前跳 1 到 m 步
            for (int j = 1; j <= m; ++j) {
                int v = u + j;
                if (v >= len) break; // 跳出界了
                if (s_aug[v] == 'C') continue; // 不能跳到鳄鱼上！

                if (s_aug[v] == 'L') { // 跳到另一个表面
                    if (current_cost < dist[v][0]) {
                        dist[v][0] = current_cost;
                        q.push_front({v, 0}); // 0代价边，加到队头
                    }
                } else { // 跳进水里 ('W')
                    if (current_cost < dist[v][1]) {
                        dist[v][1] = current_cost;
                        q.push_front({v, 1}); // 0代价边，加到队头
                    }
                }
            }
        } else { // 在水里
            // 只能游到下一个位置
            int v = u + 1;
            if (v >= len) continue; // 游出界了
            if (s_aug[v] == 'C') continue; // 前面是鳄鱼，游不过去

            int new_cost = current_cost + 1;
            if (new_cost > k) continue; // 体力不支啦，不能再游了

            if (s_aug[v] == 'L') { // 游到表面
                if (new_cost < dist[v][0]) {
                    dist[v][0] = new_cost;
                    q.push_back({v, 0}); // 1代价边，加到队尾
                }
            } else { // 游到更多的水里 ('W')
                if (new_cost < dist[v][1]) {
                    dist[v][1] = new_cost;
                    q.push_back({v, 1}); // 1代价边，加到队尾
                }
            }
        }
    }

    // 检查是否能到达右岸(位置 n+1)。右岸是表面，所以看 dist[n+1][0]
    // 并且总游泳距离不能超过 k
    if (dist[n + 1][0] <= k) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码分析小贴士：

s_aug = "L" + s + "L": 这是一个非常优雅的技巧！通过在原始字符串前后各加一个 'L'，我们把起点（左岸）和终点（右岸）也视作木头。这样就不用为边界情况写额外的判断了，代码变得非常统一和简洁。
dist 数组: dist[i][0] 和 dist[i][1] 分别记录到达位置 i 的两种不同介质状态的最小游泳距离。这是状态表示的核心。
deque 的使用: push_front 和 push_back 的巧妙运用是 0-1 BFS 的精髓。它确保了我们总是先探索游泳距离更短的路径。
剪枝: if (new_cost > k) continue; 是一个重要的优化。当我们发现某条路径的游泳开销已经超出了预算 k，就没必要再沿着这条路走下去了，直接放弃，可以节省很多计算哦。
最终判断: 搜索结束后，我们只需要检查到达终点 n+1（这是一个表面）的最小游泳距离 dist[n+1][0] 是否在 k 的预算内。如果在，那就说明 ErnKor 可以成功抵达对岸，YES, nya! 否则就是 NO, 太可惜了~

题目大意

解题思路

题解代码与分析

代码分析小贴士：

相关知识点介绍

0-1 广度优先搜索 (0-1 BFS)

题目大意 ​

解题思路 ​

题解代码与分析 ​

代码分析小贴士： ​

相关知识点介绍 ​

0-1 广度优先搜索 (0-1 BFS) ​

题目大意

解题思路

题解代码与分析

代码分析小贴士：

相关知识点介绍

0-1 广度优先搜索 (0-1 BFS)