传送门 // 题意: 给定两个体积的杯子, 有如题的三种操作, 问能否倒出来给定的一个体积水. 输出最少的步骤和具体的操作步骤.
// 思路: 这道题的难点在于操作路径, 不能用记录前驱的方法来解决, 因为同一个步骤可能会有多个相同的前驱, 也就是不好操作. 那么最好的方法就是把到这一步之前的步全部保存下来, 然后一一输出即可. 然后其他的步骤和非常可乐很像啦, 直接bfs搜搜即可….
AC Code
const int maxn = 1e2+5; int vis[maxn][maxn]; struct node { int x, y, step; string s; // 保存步骤的. }; string str[] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; int A, B, ed; void solve() { scanf("%d%d%d", &A, &B, &ed); vis[0][0] = 1; queue<node>q; q.push(node{0, 0, 0, ""}); while(!q.empty()) { node u = q.front(); q.pop(); if (u.x == ed || u.y == ed) { cout << u.step << endl; for (int i = 0 ; i < u.step ; i ++) { cout << str[u.s[i] - '0'] << endl; } return ; } if (u.x < A) { // 装满第一个 node k = u; k.x = A; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '0'}); } } if (u.y < B) { // 装满第二个 node k = u; k.y = B; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '1'}); } } if (u.x) { // 倒掉第一个 node k = u; k.x = 0; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '2'}); } } if (u.y) { // 倒掉第二个 node k = u; k.y = 0; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '3'}); } } if (u.x && u.y < B) { // 第一个往第二个里面倒 node k = u; if (B - u.y >= u.x) k.y += k.x, k.x = 0; else k.x -= B - k.y, k.y = B; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '4'}); } } if (u.y && u.x < A) { // 第二个往第一个里面倒 node k = u; if (A - u.x >= u.y) k.x += k.y, k.y = 0; else k.y -= A - k.x, k.x = A; if (!vis[k.x][k.y]) { vis[k.x][k.y] = 1; q.push(node{k.x, k.y, u.step+1, u.s + '5'}); } } } printf("impossible\n"); }