CSP-S 提高级 · CSP 2022 提高级第一轮 第 20 题

(2)（容器分水） 有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：

1. FILL(i)：用水龙头将容器 $i(i \in {1,2})$ 灌满水； 2. DROP(i)：将容器 i 的水倒进下水道； 3. POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。

试补全程序。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int f[N][N];
int ans;
int a, b, c;
int init;

int dfs(int x, int y) {
    if (f[x][y] != init)
        return f[x][y];
    if (x == c || y == c)
        return f[x][y] = 0;
    f[x][y] = init - 1;
    f[x][y] = min(f[x][y], dfs(a, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, b) + 1);
    f[x][y] = min(f[x][y], dfs(0, y) + 1);
    f[x][y] = min(f[x][y], dfs(x, 0) + 1);
    int t = min(a - x, y);
    f[x][y] = min(f[x][y], ①);
    t = min(x, b - y);
    f[x][y] = min(f[x][y], ②);
    return f[x][y];
}

void go(int x, int y) {
    if (③)
        

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是求两个容器间状态转移的最短路，但题目强制用 DFS 记忆化来算。拿到题先想：状态是 (x, y)，终点是 x=c 或 y=c，所有操作代价都是 1，所以 dfs(x, y) = 1 + min(所有后继状态的 dfs)。填空时盯着代码里已写好的 FILL/DROP 都是 +1，POUR 同理，方向搞反容易掉坑。

最容易错在①和②把 POUR 的方向搞混：t = min(a - x, y) 是从 2 倒到 1，新状态是 (x + t, y - t)，对应 dfs(x + t, y - t) + 1；而 t = min(x, b - y) 是从 1 倒到 2，新状态是 (x - t, y + t)，对应 dfs(x - t, y + t) + 1。③处若写成 && 就错了，只要一个容器达到 c 就算成功。④⑤在 go 函数里顺序要和 dfs 里一致，否则输出的操作序列会乱。

这道题考查的是搜索——DFS 记忆化求最短路径，同时涉及状态转移的正确建模和边界条件的判断。

首先把题意翻译成状态：两个容器的水量分别是 x 和 y，状态就是 (x, y)。目标是让 x = c 或 y = c。一共有六种操作：灌满 1、灌满 2、倒空 1、倒空 2、从 2 倒到 1、从 1 倒到 2。每种操作都算一步，所以我们要找的是从 (0,0) 到任意满足条件的状态的最少步数。

题目给的 dfs 框架已经写好了：

• 用 f[x][y] 存结果，init 是一个很大的数（127），用来判断是否计算过。
• 遇到已计算过的直接返回。
• 如果 x == c 或 y == c，说明已经达成目标，步数为 0。
• 否则先标记 f[x][y] = init - 1，防止在递归过程中重复访问同一个状态（因为图里可能有环）。
• 然后依次尝试六种操作，每次调用 dfs(新状态) + 1，取最小值。

现在逐空分析：

① 这里对应的是 POUR(2,1)，也就是从容器 2 往容器 1 倒水。代码里先算 t = min(a - x, y)，意思是 1 号还能装 a - x 升，2 号有 y 升，所以最多能倒 min(a - x, y)。倒完后，1 号变成 x + t，2 号变成 y - t。因为这是多了一步操作，所以是 dfs(x + t, y - t) + 1。选项 A 正确。

② 这里对应 POUR(1,2)，方向相反。t = min(x, b - y)，1 号有 x 升，2 号还能装 b - y 升。倒完后 1 号减少 t，2 号增加 t，即 (x - t, y + t)。同样是 +1。选项 C 正确。

③ 这是终止条件。题目要求获得恰好 c 升水，只要任意一个容器达到 c 就成功了，不需要两个同时达到。所以是 ||，选项 A 正确。

④ go 函数负责输出操作序列。它从初始状态 (0,0) 开始，判断当前状态 f[x][y] 是由哪个后继状态转移来的。前面 dfs 里先处理 POUR(2,1)，所以这里先检查是否等于 dfs(x + t, y - t) + 1，也就是选项 A。

⑤ 同理，后面处理 POUR(1,2)，检查是否等于 dfs(x - t, y + t) + 1，即选项 C。

为什么不用 BFS？理论上 BFS 更直观，但题目强制用 DFS 记忆化，这也是竞赛里常见的套路：用 dfs 求最短路径等价于 DP，只要边权都是 1，结果一样。关键是理解 f[x][y] = init - 1 这个标记的作用，防止死循环。

易错点总结：

• POUR 的两个方向容易记反，一定要看 t 的计算公式：a - x 说明 1 号还有空间，所以是从 2 倒到 1；b - y 说明 2 号还有空间，所以是从 1 倒到 2。
• 终止条件用 && 就错了，因为只要一个容器达到 c 就行。
• go 里的顺序要和 dfs 里一致，否则输出的操作序列会乱。
• 所有操作都是 +1，没有 -1 的情况，选项里带 -1 的都是干扰项。

考频与趋势：DFS 在题库里共考过 61 题，覆盖 7 个考试级别（2009-2026），其中 2024 年考了 13 题、2025 年 9 题、2026 年 22 题，近年明显增多；分赛事看，GESP 七级 20 题、六级 16 题、八级 11 题，CSP 提高级也有 5 题。这类“求最少步数 + 输出序列”的搜索题在 CSP 提高级和 GESP 高级别中很受欢迎，未来大概率还会以类似形式出现，比如增加更多容器或更复杂的操作限制。暂无足够依据预测具体年份的题号分布，但 DFS 记忆化求最短路径这个考点本身会持续高频。

综上，正确填空依次为：① A、② C、③ A、④ A、⑤ C。