1631 - Jugs

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.

You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.

A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are

fill A

    fill B
    empty A
    empty B
    pour A B
    pour B A
    success

&nbsp;&nbsp;&nbsp; where "pour A B" means "pour the contents of jug A into jug B", and "success" means that the goal has been accomplished.

&nbsp;&nbsp;&nbsp; You may assume that the input you are given does have a solution.

<span id="1360921774759S">&nbsp;</span>

题目输入

Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are relatively prime to one another.

题目输出

Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line "success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.

输入/输出样例

输入格式

3 7 1
9 32 6

输出格式

fill B
pour B A
empty A
pour B A
success
fill B
pour B A
empty A
pour B A
empty A
pour B A
empty A
pour B A
fill B
pour B A
empty A
pour B A
empty A
pour B A
empty A
pour B A
empty A
pour B A
fill B
pour B A
empty A
pour B A
empty A
pour B A
success

C语言解答

#include<stdio.h>
#include<stdlib.h>
char cz[6][20]={"fill A","fill B","empty A","empty B","pour A B","pour B A"};
int op[10000];//记录步骤
int count;
int n,ca,cb;//需求量,a容量,b容量
typedef struct
{
	int a;//当前a的容量
	int b;//当前b的容量
	int step;//层数
}node;
typedef struct
{
	node data[10000];
	int front;
	int rear;
}cqueue;//存放水杯状态的队列
int isempty(cqueue*a)
{
	if(a->front==a->rear)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
void empty(cqueue*a)
{
	a->rear=a->front=-1;
}
void push(cqueue*a,node x)
{
	a->rear++;
	a->data[a->rear]=x;
}
void pop(cqueue*a)
{
	a->front++;
}
int**hash;//记录是否达到过两瓶水当前容量这个状态;
cqueue num;//存放状态节点的队列
cqueue*numm=&num;
node Node;//充当节点临时变量

node**hash2;//记录达到两瓶水当前容量这个状态的前一个状态;
int**hash3;//记录达到两瓶水当前容量这个状态的前一个操作;
void print()
{
	int i;
	for(i=0;i<count;i++)
	{
		if(op[i]==0)
		{
			printf("fill A\n");
		}
		if(op[i]==1)
		{
			printf("fill B\n");
		}
		if(op[i]==2)
		{
			printf("empty A\n");
		}
		if(op[i]==3)
		{
			printf("empty B\n");
		}
		if(op[i]==4)
		{
			printf("pour A B\n");
		}
		if(op[i]==5)
		{
			printf("pour B A\n");
		}
	}
	printf("success\n");
}//用于输出路径，暂时还没用上
void bfs()
{
	node temp;//当前队首元素
	int i;
	while(!isempty(numm))//当队列不为空
	{
		temp=numm->data[numm->front+1];//取出队首元素
		pop(numm);//出队
		if(temp.b==n)//如果满足条件，函数结束
		{
			Node.a=temp.a;
			Node.b=temp.b;
			Node.step=temp.step;
			return ;
		}
		for(i=0;i<6;i++)//6种情况分别选择
		{
			if(i==0)//fill A
			{
				Node.a=ca;
				Node.b=temp.b;//给完成倒水操作的相邻状态赋值
				Node.step=temp.step+1;//相邻节点层数加1
				if(hash[Node.a][Node.b]==0)//如果这个操作结束后的状态已经进入过队列，就不把这种情况入队,否则，进入并把标志置1
				{
					push(numm,Node);
				    hash[Node.a][Node.b]=1;
					hash2[Node.a][Node.b]=temp;
					hash3[Node.a][Node.b]=0;
				}
			}
			if(i==1)//fill B
			{
				Node.a=temp.a;
				Node.b=cb;
				Node.step=temp.step+1;
				if(hash[Node.a][Node.b]==0)
				{
					push(numm,Node);
				    hash[Node.a][Node.b]=1;
					hash2[Node.a][Node.b]=temp;
					hash3[Node.a][Node.b]=1;
				}
			}
			if(i==2)//empty A
			{
				Node.a=0;
				Node.b=temp.b;
				Node.step=temp.step+1;
				if(hash[Node.a][Node.b]==0)
				{
					push(numm,Node);
				    hash[Node.a][Node.b]=1;
					hash2[Node.a][Node.b]=temp;
					hash3[Node.a][Node.b]=2;
				}
			}
			if(i==3)//empty B
			{
				Node.a=temp.a;
				Node.b=0;
				Node.step=temp.step+1;
				if(hash[Node.a][Node.b]==0)
				{
					push(numm,Node);
				    hash[Node.a][Node.b]=1;
					hash2[Node.a][Node.b]=temp;
					hash3[Node.a][Node.b]=3;
				}
			}
			if(i==4)//pour A B
			{
				if(temp.a>cb-temp.b)
				{
					Node.b=cb;
					Node.a=temp.a-cb+temp.b;
					Node.step=temp.step+1;
					if(hash[Node.a][Node.b]==0)
					{
					   	push(numm,Node);
				       	hash[Node.a][Node.b]=1;
						hash2[Node.a][Node.b]=temp;
						hash3[Node.a][Node.b]=4;
					}
				}
				else
				{
					Node.b=temp.a+temp.b;
					Node.a=0;
					Node.step=temp.step+1;
					if(hash[Node.a][Node.b]==0)
					{
					   	push(numm,Node);
				       	hash[Node.a][Node.b]=1;
						hash2[Node.a][Node.b]=temp;
						hash3[Node.a][Node.b]=4;
					}
				}
			}
			if(i==5)//pour B A
			{
				if(temp.b>ca-temp.a)
				{		
					Node.a=ca;
					Node.b=temp.b-ca+temp.a;
					Node.step=temp.step+1;
					if(hash[Node.a][Node.b]==0)
					{	
					   	push(numm,Node);
				       	hash[Node.a][Node.b]=1;
						hash2[Node.a][Node.b]=temp;
						hash3[Node.a][Node.b]=5;
					}
				}
				else
				{
					Node.a=temp.b+temp.a;
					Node.b=0;
					Node.step=temp.step+1;
					if(hash[Node.a][Node.b]==0)
					{
					   	push(numm,Node);
				       	hash[Node.a][Node.b]=1;
						hash2[Node.a][Node.b]=temp;
						hash3[Node.a][Node.b]=5;
					}
				}
			}
		}//6种情况的节点均已入队列,该节点的相邻节点遍历结束
	}
}
int main()
{
	int i,j;
	while(scanf("%d %d %d",&ca,&cb,&n)!=EOF)
	{
		empty(numm);//清空队列
		hash=(int**)malloc(sizeof(int*)*(ca+1));
		hash2=(node**)malloc(sizeof(node*)*(ca+1));
		hash3=(int**)malloc(sizeof(int*)*(ca+1));
		for(i=0;i<ca+1;i++)
		{
			hash[i]=(int*)malloc(sizeof(int)*(cb+1));
			hash2[i]=(node*)malloc(sizeof(node)*(cb+1));
			hash3[i]=(int*)malloc(sizeof(int)*(cb+1));
		}
		for(i=0;i<ca+1;i++)
		{
			for(j=0;j<cb+1;j++)
			{
				hash[i][j]=0;//将所有标志位清零
			}
		}
		Node.a=0;
		Node.b=0;
		hash[0][0]=1;
		Node.step=0;//更新开始状态
		push(numm,Node);
		bfs();
		count=Node.step;
		for(i=count-1;i>=0;i--)
		{
			op[i]=hash3[Node.a][Node.b];
			Node=hash2[Node.a][Node.b];
		}
		print();
		//printf("%d\n",Node.step);
	}
	return 0;
}

C++解答

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct JUG
{
	int ca,cb,a[1000],k;
}start,head,tail;

char s[6][9]={"fill A","fill B","empty A","empty B","pour A B","pour B A"};
int ca,cb,n,v[1001][1001];

void bfs()
{
	memset(v,0,sizeof(v));
	queue<JUG> q;
	q.push(start);
	v[start.ca][start.cb]=1;
	while(!q.empty())
	{
		head=q.front();
		q.pop();

		if(head.ca==n||head.cb==n)
			return;

		tail=head;
		tail.ca=ca;
		if(!v[tail.ca][tail.cb])
		{
			v[tail.ca][tail.cb]=1;
			tail.a[tail.k]=0;
			tail.k++;
			q.push(tail);
		}

		tail=head;
		tail.cb=cb;
		if(!v[tail.ca][tail.cb])
		{
			v[tail.ca][tail.cb]=1;
			tail.a[tail.k]=1;
			tail.k++;
			q.push(tail);
		}

		tail=head;
		tail.ca=0;
		if(!v[tail.ca][tail.cb])
		{
			v[tail.ca][tail.cb]=1;
			tail.a[tail.k]=2;
			tail.k++;
			q.push(tail);
		}

		tail=head;
		tail.cb=0;
		if(!v[tail.ca][tail.cb])
		{
			v[tail.ca][tail.cb]=1;
			tail.a[tail.k]=3;
			tail.k++;
			q.push(tail);
		}

		tail=head;
		if(tail.ca&&tail.cb<cb)
		{
			if(tail.ca<=cb-tail.cb)
			{
				tail.cb+=tail.ca;
				tail.ca=0;
				if(!v[tail.ca][tail.cb])
				{
					v[tail.ca][tail.cb]=1;
					tail.a[tail.k]=4;
					tail.k++;
					q.push(tail);
				}
			}
			else
			{
				tail.ca-=cb-tail.cb;
				tail.cb=cb;
				if(!v[tail.ca][tail.cb])
				{
					v[tail.ca][tail.cb]=1;
					tail.a[tail.k]=4;
					tail.k++;
					q.push(tail);
				}
			}
		}

		tail=head;
		if(tail.cb&&tail.ca<ca)
		{
			if(tail.cb<=ca-tail.ca)
			{
				tail.ca=+tail.cb;
				tail.cb=0;
				if(!v[tail.ca][tail.cb])
				{
					v[tail.ca][tail.cb]=1;
					tail.a[tail.k]=5;
					tail.k++;
					q.push(tail);
				}
			}
			else
			{
				tail.cb-=ca-tail.ca;
				tail.ca=ca;
				if(!v[tail.ca][tail.cb])
				{
					v[tail.ca][tail.cb]=1;
					tail.a[tail.k]=5;
					tail.k++;
					q.push(tail);
				}
			}
		}
		
	}
}

int main()
{
	int i;
	while(scanf("%d%d%d",&ca,&cb,&n)!=EOF)
	{
		start.ca=start.cb=start.k=0;
		bfs();
		for(i=0;i<head.k;i++)
			puts(s[head.a[i]]);
		puts("success");
	}
	return 0;
}

上一题下一题提示代码讨论统计