题目链接
http://poj.org/problem?id=1606
题意
有两个容量分别为ca,cb的杯子，可以向杯子里倒水，将杯子里的水倒空，将一个杯子里的水倒到另一个杯子里，求怎样倒才能使其中的一个杯子里的水恰为N加仑。
思路
两个杯子里的水量组成一个状态，不断地进行题中的6种操作来扩展状态结点进行bfs，直到其中一个杯子的水量为N即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std; struct Node
{
int a, b;
int flag;
Node* pre;
}; const int N = ;
int ca, cb, n;
int visit[N][N];
stack<int> s; void print()
{
while (!s.empty())
{
switch (s.top())
{
case :
cout << "fill A" << endl;
break;
case :
cout << "fill B" << endl;
break;
case :
cout << "empty A" << endl;
break;
case :
cout << "empty B" << endl;
break;
case :
cout << "pour A B" << endl;
break;
case :
cout << "pour B A" << endl;
break;
}
s.pop();
}
cout << "success" << endl;
} void bfs(int a, int b)
{
Node state[N];
int cnt = -;
memset(visit, , sizeof(visit));
Node node;
node.a = node.b = ;
node.pre = NULL;
queue<Node> q;
q.push(node);
visit[node.a][node.b] = ;
while (!q.empty())
{
Node node = q.front();
q.pop();
state[++cnt] = node;
Node next = node;
for (int i = ; i < ; i++)
{
next = node;
int amount;
switch (i)
{
case : //fill a
next.a = ca;
next.flag = ;
break;
case : //fill b
next.b = cb;
next.flag = ;
break;
case : // empty a
next.a = ;
next.flag = ;
break;
case : //empty b
next.b = ;
next.flag = ;
break;
case : //pour a b
amount = cb - node.b;
if (node.a > amount)
{
next.a -= amount;
next.b = cb;
}
else {
next.a = ;
next.b = node.a + node.b;
}
next.flag = ;
break;
case : //pour b a
amount = ca - node.a;
if (node.b > amount)
{
next.a = ca;
next.b -= amount;
}
else {
next.a = node.a + node.b;
next.b = ;
}
next.flag = ;
break;
} if (!visit[next.a][next.b])
{
visit[next.a][next.b] = ;
next.pre = &state[cnt];
if (next.a==n || next.b == n)
{
while (next.pre)
{
s.push(next.flag);
next = *next.pre;
}
print();
return;
}
q.push(next);
}
}
}
} int main()
{
//freopen("poj1606.txt", "r", stdin);
while (cin >> ca >> cb >> n)
{
bfs(, );
}
return ;
}
相似题目