3

我需要帮助解决这个问题POUR1。我认为它可以用蛮力方法解决，但我读到这是一个图形问题（BFS）。我解决了 ABCPATH、LABYR1、PT07Y、PT07Z、BITMAP 等问题……
但我不知道如何以 BFS 方式处理 POUR1。

有人可以给我一些建议吗？

问题陈述：

给定两个容器，其中一个可以容纳 1 升水，另一个可以容纳 b 升水，确定在其中一个容器中准确获得 c 升水所需的步骤数。

开始时，两个容器都是空的。以下操作计为“步数”：

  • 清空容器，
  • 填充容器，
  • 将水从一个容器倒到另一个容器中，不要溢出，直到其中一个容器满或空。

输入：

一个整数t，1<=t<=100，表示测试用例的个数，后面跟着t组输入数据，每组由三个不大于40000的正整数a、b、c组成，分行给出。

输出：

对于每组输入数据，输出获得 c 升所需的最小步数，如果不可能，则输出 -1。

例子：

样本输入：

2
5
2
3
2
3
4

样本输出：

2
-1
4

2 回答 2

15

这个问题有一个更简单的解决方案。不需要 BFS。Ad-hoc 会做得很好。方法1-填充A，将其清空到B中。每当A变空时，将其重新填充，每当B变满时，将其清空。（所有上述动作都算作单独的动作）。继续此过程，直到您在任何一个容器中达到所需的水量。在此处获取移动次数。（说C1）。
方法2-填充B，将其清空到A中。每当B变空时，将其重新填充，每当A变满时，将其清空。继续此操作，直到您达到所需的金额。获取移动数说C2）。
答案是min(C1,C2)。
C++源代码：

#include < cstdio > 
#include < algorithm >
using namespace std;

int pour(int A, int B, int C) {
  int move = 1, a = A, b = 0, tfr;
  while (a != C && b != C) {
    tfr = min(a, B - b);
    b += tfr;
    a -= tfr;
    move++;
    if (a == C || b == C)
      break;
    if (a == 0) {
      a = A;
      move++;
    }
    if (b == B) {
      b = 0;
      move++;
    }
  }
  return move;
}
/** Reason for calculating GCD of a,b is to check whether an integral solution of 
 *  equation of form ax + by = c exist or not, to dig deeper read Diophantine Equations
 */
int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
int main() {
  int t, a, b, c;
  scanf("%d", & t);
  while (t--) {
    scanf("%d%d%d", & a, & b, & c);
    if (c > a && c > b)
      printf("-1\n");
    else if (c % gcd(a, b) != 0)
      printf("-1\n");
    else if (c == a || c == b)
      printf("1\n");
    else
      printf("%d\n", min(pour(a, b, c), pour(b, a, c)));
  }
  return 0;
}
于 2013-10-21T17:03:26.827 回答
5

考虑所有先验可能状态的集合（例如 [3, 7] 意味着 Vessel1 包含 3 窝，vessel2 包含 7 窝）。您有一个有向图，其顶点是那些状态，其边是可能的移动。问题是在图中找到一条路径，将状态 [0, 0] 连接到 [c, ?] 类型的状态或 [?, c] 类型的状态。这样的路径通常由 BFS 搜索。

于 2013-07-25T22:07:29.303 回答