分油问题

Description

设有大小不等的３个无刻度的油桶，分别能盛满 X、Y、Z(都小于等于 100)升油，初始时第一个油桶盛满，另外两个为空。现在，要想在某一瓶中分出 T升油。分油时可把一个桶里的油倒入另外的桶中，或者将桶中的油倒空。设计一种以最少步骤的分油方案。

Input

第一行：X Y Z {设第一个油桶 X 已装满油} 第二行：T {要分出的目标油量}

Output

输出最少步数，若无法分出 T 升油，则输出“NO ANSWER! ” 。

Sample Input

80 50 30 60

Sample Output

3

Source

BFS，枚举

Solution

分情况讨论从每一个油壶里倒油的情况，用队列实现搜索

Code

#include <cstdio>#include <algorithm>#include <queue>using namespace std;int x, y, z, t;int p[101][101][101];queue <int> a, b, c, ans;bool bj;int main() {  scanf("%d %d %d %d", &x, &y, &z, &t);  if (x < t) {PRintf("NO ANSWER!/n"); return 0;}  a.push(x), b.push(0), c.push(0), ans.push(0);  do {    int a1 = a.front(), b1 = b.front(), c1 = c.front(), d1 = ans.front();    if (a1 == t || b1 == t || c1 == t) {bj = true; break;}    if (a1 > 0) {      if (p[a1 - min(a1, y - b1)][b1 + min(a1, y - b1)][c1] == 0 && y > b1)//1 --> 2	a.push(a1 - min(a1, y - b1)), b.push(b1 + min(a1, y - b1)), c.push(c1), ans.push(d1 + 1),	p[a1 - min(a1, y - b1)][b1 + min(a1, y - b1)][c1] = 1;      if (p[a1 - min(a1, z - c1)][b1][c1 + min(a1, z - c1)] == 0 && z > c1)//1 --> 3	a.push(a1 - min(a1, z - c1)), b.push(b1), c.push(c1 + min(a1, z - c1)), ans.push(d1 + 1),	p[a1 - min(a1, z - c1)][b1][c1 + min(a1, z - c1)] = 1;      if (p[0][b1][c1] == 0)//empty	a.push(0), b.push(b1), c.push(c1), ans.push(d1 + 1), p[0][b1][c1] = 1;    }    if (b1 > 0) {      if (p[a1 + min(b1, x - a1)][b1 - min(b1, x - a1)][c1] == 0 && x > a1)//2 --> 1	a.push(a1 + min(b1, x - a1)), b.push(b1 - min(b1, x - a1)), c.push(c1), ans.push(d1 + 1),	p[a1 + min(b1, x - a1)][b1 - min(b1, x - a1)][c1] = 1;      if (p[a1][b1 - min(b1, z - c1)][c1 + min(b1, z - c1)] == 0 && z > c1)//2 --> 3	a.push(a1), b.push(b1 - min(b1, z - c1)), c.push(c1 + min(b1, z - c1)), ans.push(d1 + 1),	p[a1][b1 - min(b1, z - c1)][c1 + min(b1, z - c1)] = 1;      if (p[a1][0][c1] == 0)//empty	a.push(a1), b.push(0), c.push(c1), ans.push(d1 + 1), p[a1][0][c1] = 1;    }    if (c1 > 0) {      if (p[a1 + min(c1, x - a1)][b1][c1 - min(c1, x - a1)] == 0 && x > a1)//3 --> 1	a.push(a1 + min(c1, x - a1)), b.push(b1), c.push(c1 - min(c1, x - a1)), ans.push(d1 + 1),	p[a1 + min(c1, x - a1)][b1][c1 - min(c1, x - a1)] = 1;      if (p[a1][b1 + min(c1, y - b1)][c1 - min(c1, y - b1)] == 0 && y > b1)//3 --> 2	a.push(a1), b.push(b1 + min(c1, y - b1)), c.push(c1 - min(c1, y - b1)), ans.push(d1 + 1),	p[a1][b1 + min(c1, y - b1)][c1 - min(c1, y - b1)] = 1;      if (p[a1][b1][0] == 0)//empty	a.push(a1), b.push(b1), c.push(0), ans.push(d1 + 1), p[a1][b1][0] = 1;    }    a.pop(), b.pop(), c.pop(), ans.pop();  } while(!a.empty());  if (bj == true) printf("%d/n", ans.front());  else printf("NO ANSWER!/n");  return 0;}
Summary
一开始被OJ上的输出欺骗了，NO ANSWER!中的“!”是英文的不是中文的，但是题目中说是中文的，WA了一次