c++ - 对 SPOJ 上的 POUR1 有什么建议？

Question

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

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

问题陈述:

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

一开始两个容器都是空的。以下操作计为“步骤”:

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

输入:

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

输出:

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

示例:

示例输入:

2
5
2
3
2
3
4

示例输出:

2
-1

Answer 1

这个问题有一个更简单的解决方案。不需要 BFS。临时会做的很好。 方法 1 - 填充 A，将其清空到 B。每当 A 变空时将其填回，每当 B 变满时将其清空。 (上述所有 Action 都算作个人 Action )。继续这个过程，直到你在任何一个容器中达到所需的水量。在此处获取移动次数。 (比如 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;
}