本題的題意大致是：給你兩個(gè)容器，指定它們的容量Ca,Cb,還有一個(gè)目標(biāo)容量N;
兩個(gè)容器初始含水量都是零，問(wèn)如何配制出容量為N的液體；
我的做法很簡(jiǎn)單 BFS搜索，不過(guò)代碼實(shí)在太長(zhǎng) 在網(wǎng)上搜了一下 居然有一個(gè)500+B的代碼 看得不是很明白 希望有牛人能夠指點(diǎn)一下
//This is the source code for Problem POJ 1606
#include<iostream>
#include<cmath>
#include<cstring>
#include<stack>
using namespace std;
struct node
{
int ca;
int cb;
int pre;
}line[100];
int hash[10000];
stack<node>mystack;
int main()
{
int a,b,c;
int front;
int rear;
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
memset(hash,0,sizeof(hash));
while(mystack.empty()!=true)
mystack.pop();
node temp;
temp.ca=0;
temp.cb=0;
temp.pre=-1;
line[1]=temp;
front=1;
rear=1;
while(front<=rear)
{
if(line[front].ca==c||line[front].cb==c)
break;
else if(line[front].ca!=a)
{
node temp;
temp.ca=a;
temp.cb=line[front].cb;
temp.pre=front;
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
if(line[front].cb!=b)
{
node temp;
temp.cb=b;
temp.ca=line[front].ca;
temp.pre=front;
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
if(line[front].ca!=0)
{
node temp;
temp.ca=0;
temp.cb=line[front].cb;
temp.pre=front;
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
if(line[front].cb!=0)
{
node temp;
temp.cb=0;
temp.ca=line[front].ca;
temp.pre=front;
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
if(line[front].ca!=0&&line[front].cb!=b)
{
node temp;
if(b-line[front].cb>=line[front].ca)
{
temp.ca=0;
temp.cb=line[front].cb+line[front].ca;
temp.pre=front;
}
else
{
temp.ca=line[front].ca-(b-line[front].cb);
temp.cb=b;
temp.pre=front;
}
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
if(line[front].ca!=a&&line[front].cb!=0)
{
node temp;
if(a-line[front].ca>=line[front].cb)
{
temp.cb=0;
temp.ca=line[front].ca+line[front].cb;
temp.pre=front;
}
else
{
temp.cb=line[front].cb-(a-line[front].ca);
temp.ca=a;
temp.pre=front;
}
//給出下一個(gè)狀態(tài)
int hashnum=temp.ca*10+temp.cb;
if(hash[hashnum]==0)
{
hash[hashnum]=1;
rear++;
line[rear]=temp;
}//判重
}
front++;
}
int tempnum=front;
while(line[tempnum].pre!=-1)
{
mystack.push(line[tempnum]);
tempnum=line[tempnum].pre;
}
node tempnode1;
tempnode1.ca=0;
tempnode1.cb=0;
tempnode1.pre=-1;
node tempnode2;
while(mystack.empty()!=true)
{
tempnode2=mystack.top();
mystack.pop();
if(tempnode1.ca!=0&&tempnode2.ca==0&&(tempnode1.cb==tempnode2.cb))
printf("empty A\n");
else if(tempnode1.cb!=0&&tempnode2.cb==0&&(tempnode1.ca==tempnode2.ca))
printf("empty B\n");
else if(tempnode1.ca!=a&&tempnode2.ca==a&&(tempnode1.cb==tempnode2.cb))
printf("fill A\n");
else if(tempnode1.cb!=b&&tempnode2.cb==b&&(tempnode1.ca==tempnode2.ca))
printf("fill B\n");
else if(tempnode2.ca>tempnode1.ca)
printf("pour B A\n");
else
printf("pour A B\n");
tempnode1=tempnode2;
}
printf("success\n");
}
return 0;
}
500B的代碼如下：
#include<iostream>
using namespace std;
int main()
{
int ca,cb,n;
int a,b;
while(cin>>ca>>cb>>n)
{
a=0;b=0;
while(1)
{
if(b==cb) {cout<<"empty B"<<endl;b=0;if(b==n) {cout<<"success"<<endl;break;}}
else if(a==0) {cout<<"fill A"<<endl;a=ca;if(b==n) {cout<<"success"<<endl;break;}}
else if(b+a<cb) {cout<<"pour A B"<<endl;b=b+a;a=0;if(b==n) {cout<<"success"<<endl;break;}}
else if(b+a>=cb) {cout<<"pour A B"<<endl;a=a+b-cb;b=cb;if(b==n) {cout<<"success"<<endl;break;}}
}
}
system("pause");
return 0;
}
希望大家能給我解釋一下 多謝^_^