学步园

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket
to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

/*
ID: conicoc1
LANG: C
TASK: milk3
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int Queue[10000][3];
int front=0,rear=0;
int flag[100000];
int bucket[3],temp[3];  //记录状态
int A,B,C;   //记录容量 
int BC[100];

int comp(const void *a,const void *b)
{
	int *p1,*p2;
	p1=(int*)a;
	p2=(int*)b;
	
	return *p1-*p2;	
}

void AtoB()
{
	bucket[1]+=bucket[0];
	bucket[0]=0;
	if(bucket[1]>B)
	{
		bucket[0]=bucket[1]-B;
		bucket[1]=B;
	}
}

void AtoC()
{
	bucket[2]+=bucket[0];
	bucket[0]=0;
	if(bucket[2]>C)
	{
		bucket[0]=bucket[2]-C;
		bucket[2]=C;
	}
}

void BtoC()
{
	bucket[2]+=bucket[1];
	bucket[1]=0;
	if(bucket[2]>C)
	{
		bucket[1]=bucket[2]-C;
		bucket[2]=C;
	}
}

void BtoA()
{
	bucket[0]+=bucket[1];
	bucket[1]=0;
	if(bucket[0]>A)
	{
		bucket[1]=bucket[0]-A;
		bucket[0]=A;
	}
}

void CtoA()
{
	bucket[0]+=bucket[2];
	bucket[2]=0;
	if(bucket[0]>A)
	{
		bucket[2]=bucket[0]-A;
		bucket[0]=A;
	}
}

void CtoB()
{
	bucket[1]+=bucket[2];
	bucket[2]=0;
	if(bucket[1]>B)
	{
		bucket[2]=bucket[1]-B;
		bucket[1]=B;
	}
}

void act(int i)
{
	switch(i)
	{
		case 1:AtoB();break;
		case 2:AtoC();break;
		case 3:BtoA();break;
		case 4:BtoC();break;
		case 5:CtoA();break;
		case 6:CtoB();break;
	}		
}

void Enqueue()
{
	int i;
	for(i=0;i<3;i++)
	{
		Queue[rear][i]=bucket[i];		
	}
	rear++;
}

void Dequeue()
{
	int i;
	for(i=0;i<3;i++)
	{
		bucket[i]=Queue[front][i];
	}
	front++;
}


int main()
{
	FILE *fin,*fout;
	fin=fopen("milk3.in","r");
	fout=fopen("milk3.out","w");
	
	memset(flag,-1,sizeof(flag));
	
	fscanf(fin,"%d %d %d",&A,&B,&C);
	
	int i,j,k=0;
	
	bucket[0]=0;
	bucket[1]=0;
	bucket[2]=C;
	
	
	Enqueue();
	flag[bucket[0]+bucket[1]*21+bucket[2]*21*21]=1;
	
	while(front!=rear)
	{
		Dequeue();
		for(j=0;j<3;j++)
			temp[j]=bucket[j];
		
		for(i=1;i<=6;i++)
		{
			act(i);
			if(flag[bucket[0]+bucket[1]*21+bucket[2]*21*21]!=1)
			{
				Enqueue();
				flag[bucket[0]+bucket[1]*21+bucket[2]*21*21]=1;
			}
			for(j=0;j<3;j++)
				bucket[j]=temp[j];	
		}
		if(bucket[0]==0)
		{
			BC[k++]=bucket[2];
		}	
	}
	
	qsort(BC,k,sizeof(int),comp);
	
	for(i=0;i<k-1;i++)
		fprintf(fout,"%d ",BC[i]);
	
	fprintf(fout,"%d\n",BC[k-1]);
	
	return 0;
}

不知道算不算水题？

模拟了9个时钟转的那道的BFS

问题不大