欢迎访问我的新博客：http://www.milkcu.com/blog/
原文地址：http://www.milkcu.com/blog/archives/1395211740.html
引言
这是2013年蓝桥杯全国软件大赛模拟题的第4题，问题是分红酒，方法是BFS。
题目描述
标题：分红酒
有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。
允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。这样的一次倒酒动作称为1次操作。
假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？
本题就是要求你编程实现最小操作次数的计算。
输入：最终状态（逗号分隔）
输出：最小操作次数（如无法实现，则输出-1）
例如：
输入：
9,0,0,0
应该输出：
0
输入：
6,0,0,3
应该输出：
-1
输入：
7,2,0,0
应该输出：
2
对于编程题目，要求选手给出的解答完全符合ANSI C++标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
代码中允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意选择自己使用的编译环境。
分析
这是一个关于广度优先搜索（BFS）的题目。每个杯中水的量只能为整数，所以状态是有限的，遍历这些状态，并找出距离初始状态最短的路径，即为所求解。
广度优先搜索（BFS）使用队列实现，正如深度优先搜索（DFS）使用堆栈实现。
解题思路确定了，代码实现就简单一点了，当然也会出现小错误。
程序实现
数组模拟队列
队列是一种常用的先进先出（FIFO）的数据结构，常用数组模拟实现。
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct Node {
int v[4];
int dist;
} Node;
int vis[10][10][10];
int count = 0;
int a, b, c, d;
void bfs(void) {
Node q[100000];
int front = 0;
int rear = 1;
Node state;
int cap[4] = {9, 7, 4, 2};
state.v[0] = 9;
state.v[1] = state.v[2] = state.v[3] = 0;
state.dist = 0;
q[front] = state;
vis[state.v[1]][state.v[2]][state.v[3]] = 1;
while(rear > front) {
Node olds = q[front];
if(olds.v[0] == a && olds.v[1] == b && olds.v[2] == c && olds.v[3] == d) {
cout << olds.dist << endl;
return;
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(i == j) {
continue;
}
// i to j
Node & news = q[rear];
memcpy(&news, &olds, sizeof(Node));
int amount = min(olds.v[i], cap[j] - olds.v[j]);
news.v[i] -= amount;
news.v[j] += amount;
news.dist++;
if(!vis[news.v[1]][news.v[2]][news.v[3]]) {
vis[news.v[1]][news.v[2]][news.v[3]] = 1;
rear++;
}
}
}
front++;
}
cout << "-1" << endl;
}
int main(void) {
cin >> a >> b >> c >> d;
memset(vis, 0, sizeof(vis));
bfs();
return 0;
}
STL队列实现
C++ STL标准模板库极大的提高了编程效率，虽然有时不如数组灵活，解答这个问题还是没问题的。
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef struct Node {
int v[4];
int dist;
} Node;
int vis[10][10][10];
int count = 0;
int a, b, c, d;
void bfs(void) {
queue<Node> q;
Node state;
int cap[4] = {9, 7, 4, 2};
state.v[0] = 9;
state.v[1] = state.v[2] = state.v[3] = 0;
state.dist = 0;
q.push(state);
vis[state.v[1]][state.v[2]][state.v[3]] = 1;
while(!q.empty()) {
Node olds = q.front();
q.pop();
if(olds.v[0] == a && olds.v[1] == b && olds.v[2] == c && olds.v[3] == d) {
cout << olds.dist << endl;
return;
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(i == j) {
continue;
}
// i to j
Node news;
memcpy(&news, &olds, sizeof(Node));
int amount = min(olds.v[i], cap[j] - olds.v[j]);
news.v[i] -= amount;
news.v[j] += amount;
news.dist++;
if(!vis[news.v[1]][news.v[2]][news.v[3]]) {
vis[news.v[1]][news.v[2]][news.v[3]] = 1;
q.push(news);
}
}
}
}
cout << "-1" << endl;
}
int main(void) {
cin >> a >> b >> c >> d;
memset(vis, 0, sizeof(vis));
bfs();
return 0;
}
反例分析
解决这个问题的过程也是曲折的，刚开始的时候想使用STL中以整型指针为模板的queue，但是发现队列中每次压入的指针值都是相同的，把这个反例也分享一下吧。
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int vis[10][10][10];
int count = 0;
int a, b, c, d;
void bfs(void) {
queue<int *> q;
int state[5];
int capacity[4] = {9, 7, 4, 2};
state[0] = 9;
state[1] = state[2] = state[3] = 0;
state[4] = 0;
q.push(state);
vis[state[1]][state[2]][state[3]] = 1;
while(!q.empty()) {
int * tmp = q.front();
q.pop();
int oldState[5];
memcpy(oldState, tmp, sizeof(oldState));
if(oldState[0] == a && oldState[1] == b && oldState[2] == c && oldState[3] == d) {
cout << oldState[4] << endl;
return;
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(i == j) {
continue;
}
// i to j
int newState[5];
memcpy(newState, oldState, sizeof(oldState));
int quantity = min(oldState[i], capacity[j] - oldState[j]);
newState[i] = oldState[i] - quantity;
newState[j] = oldState[j] + quantity;
cout << newState[0] << ", "
<< newState[1] << ", "
<< newState[2] << ", "
<< newState[3] << ", "
<< newState[4] << endl;
if(!vis[newState[1]][newState[2]][newState[3]]) {
vis[newState[1]][newState[2]][newState[3]] = 1;
newState[4]++;
cout << newState << endl;
q.push(newState);
}
}
}
}
cout << "-1" << endl;
}
int main(void) {
cin >> a >> b >> c >> d;
memset(vis, 0, sizeof(vis));
bfs();
return 0;
}
这个反例，在我的电脑上每次压入队列的值均为0x28fe50，这是由于变量有效期的问题。
小结
虽然文中提供了多种解决方案，但核心思想都是广度优先搜索（BFS）。
当然这个问题也可以扩展一下，把每个步骤的状态打印出来。
（全文完）