Baudelaire is Programmer

至此第1.4关通关。

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.

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.

状态空间很有限，每个桶最多有21种状态（包括桶为空），最坏情况下总状态数为21³，直接进行DFS深度优先搜索，当状态重复时剪枝，这样就遍历了三个桶所有可能的状态。DFS一般递归实现，注意不要在递归函数中过度使用全局变量（由于我使用全局变量用于循环控制，出现了问题，详情请看代码注释）。

点击以查看我的程序源码：

/*
ID: *******
LANG: C++
TASK: milk3
*/
#include<stdio.h>
#include<stdlib.h>

bool hash[21][21][21];
int cap[3];//记录容量 
FILE *fin,*fout;
int cc[21];//记录结果 
bool hashCc[21];//用于结果去重 
int tailCc;

int cmpint(const void *a, const void *b){
	return(*(int *)a-*(int *)b); //升序 
}

void dfs(int st[3]){//st[0] st[1] st[2] 分别代表A B C桶的状态 
	if(hash[st[0]][st[1]][st[2]])return;//判断该状态是否扩展过 
	hash[st[0]][st[1]][st[2]]=true;
	if(st[0]==0&&!hashCc[st[2]]){
		hashCc[st[2]]=true;
		cc[++tailCc]=st[2];
	}
	int tt[3];
	int i,j;//如果i,j为全局变量，将出现逻辑错误！这种错误很隐蔽，要注意避免在递归函数中滥用全局变量。
	for(i=0;i<3;i++)
		for(j=0;j<3;j++){//枚举各种倾倒 
			if(i==j)continue;
			tt[0]=st[0];
			tt[1]=st[1];
			tt[2]=st[2];
			if(tt[i]+tt[j]>cap[j]){
				tt[i]=tt[i]+tt[j]-cap[j];
				tt[j]=cap[j];
			}
			else{
				tt[j]+=tt[i];
				tt[i]=0;
			}
			dfs(tt);
		}
	return;
}

int main(){
	int i,j,k;
	fin=fopen("milk3.in","r");
	fout=fopen("milk3.out","w");
	fscanf(fin,"%d %d %d",&cap[0],&cap[1],&cap[2]);
	for(i=0;i<21;i++)
		for(j=0;j<21;j++)
			for(k=0;k<21;k++)
				hash[i][j][k]=false;
	for(i=0;i<21;i++)
		hashCc[i]=false;
	tailCc=-1;
	int st[3];
	st[0]=st[1]=0;
	st[2]=cap[2];
	dfs(st);
	qsort(cc,tailCc+1,sizeof(int),cmpint);
	fprintf(fout,"%d",cc[0]);
	for(i=1;i<=tailCc;i++)
		fprintf(fout," %d",cc[i]);
	fprintf(fout,"\n");
	return 0;
}