其实很简单，一个BFS就过
先放题目：node
【 问题描述】
设有大小不等的３ 个无刻度的油桶， 分别能盛满 X、 Y、 Z(都小于等于 100)
升油， 初始时第一个油桶盛满， 另外两个为空。 如今， 要想在某一瓶中分出 T
升油。 分油时可把一个桶里的油倒入另外的桶中， 或者将桶中的油倒空。 设计一
种以最少步骤的分油方案。
【 输入】
以文件方式输入数据， 格式为：
第一行： X Y Z {设第一个油桶 X 已装满油}
第二行： T {要分出的目标油量}
【 输出】
输出最少步数， 若没法分出 T 升油， 则输出“ NO ANSWER！ ”。
【 样例】
oil.in
80 50 30
60
oil.out
3
放代码web
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int x, y, z, t;
bool v[101][101][101];
struct node{
int a, b, c;
int k;
}a[7000000];
int l, r = 1;
int main()
{
freopen("oil.in","r",stdin);
freopen("oil.out","w",stdout);
scanf("%d %d %d\n%d", &x, &y, &z, &t);
a[0].a = x;
v[x][0][0] = 1;
while (l <= r)
{
v[a[l].a][a[l].b][a[l].c] = 1;
if (a[l].a != 0 && v[0][a[l].b][a[l].c] == 0)
{
a[r].a = 0;
a[r].b = a[l].b;
a[r].c = a[l].c;
a[r].k = a[l].k + 1;
r++;
}
if (a[l].b != 0 && v[a[l].a][0][a[l].c] == 0)
{
a[r].a = a[l].a;
a[r].b = 0;
a[r].c = a[l].c;
a[r].k = a[l].k + 1;
r++;
}
if (a[l].c != 0 && v[a[l].a][a[l].b][0] == 0)
{
a[r].a = a[l].a;
a[r].b = a[l].b;
a[r].c = 0;
a[r].k = a[l].k + 1;
r++;
}
if (a[l].b < y)//a -> b
{
if ((a[l].a + a[l].b) <= y && v[0][a[l].a + a[l].b][a[l].c] == 0 )
{
a[r].a = 0;
a[r].b = a[l].a + a[l].b;
a[r].c = a[l].c;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].a + a[l].b) > y && v[(a[l].a + a[l].b) - y][y][a[l].c] == 0)
{
a[r].a = (a[l].a + a[l].b) - y;
a[r].b = y;
a[r].c = a[l].c;
a[r].k = a[l].k +1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
if (a[l].c < z)//a -> c
{
if ((a[l].a + a[l].c) <= z && v[0][a[l].b][a[l].a + a[l].c] == 0)
{
a[r].a = 0;
a[r].c = a[l].a + a[l].c;
a[r].b = a[l].b;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].a + a[l].c) > z && v[(a[l].a + a[l].c) - z][a[l].b][z] == 0)
{
a[r].a = (a[l].a + a[l].c) - z;
a[r].c = z;
a[r].b = a[l].b;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
if (a[l].b < y)//c->b
{
if ((a[l].c + a[l].b) <= y && v[a[l].a][a[l].c + a[l].b][0] == 0)
{
a[r].a = a[l].a;
a[r].b = a[l].c + a[l].b;
a[r].c = 0;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].c + a[l].b) > y && v[a[l].a][y][(a[l].c + a[l].b) - y] == 0)
{
a[r].a = a[l].a;
a[r].b = y;
a[r].c = (a[l].c + a[l].b) - y;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
if (a[l].c < z)//b->c
{
if ((a[l].b + a[l].c) <= z && v[a[l].a][0][a[l].b + a[l].c] == 0)
{
a[r].a = a[l].a;
a[r].c = a[l].b + a[l].c;
a[r].b = 0;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].b + a[l].c) > z && v[a[l].a][(a[l].b + a[l].c) - z][z] == 0)
{
a[r].a = a[l].a;
a[r].c = z;
a[r].b = (a[l].b + a[l].c) - z;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
if (a[l].a < x)//b->a
{
if ((a[l].a + a[l].b) <= x && v[a[l].a+a[l].b][0][a[l].c] == 0)
{
a[r].a = a[l].a+a[l].b;
a[r].c = a[l].c;
a[r].b = 0;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].a + a[l].b) > x && v[x][0][a[(a[l].a + a[l].b) - x].c] == 0)
{
a[r].a = x;
a[r].c = a[l].c;
a[r].b = (a[l].a + a[l].b) - x;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
if (a[l].a < x)//c->a
{
if ((a[l].a + a[l].c) <= x && v[a[l].a+a[l].c][a[l].b][0] == 0)
{
a[r].a = a[l].a+a[l].c;
a[r].c = 0;
a[r].b = a[l].b;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
else
if ((a[l].a + a[l].c) > x && v[x][a[l].b][(a[l].a + a[l].c) - x] == 0)
{
a[r].a = x;
a[r].c = (a[l].a + a[l].c) - x;
a[r].b = a[l].b;
a[r].k = a[l].k + 1;
if (a[r].a == t || a[r].b == t || a[r].c == t)
{
printf("%d\n", a[r].k);
return 0;
}
r++;
}
}
l++;
}
printf("NO ANSWER!\n");
return 0;
}