8
26
2012
0

深度优先搜索:Mother's Milk

至此第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种状态(包括桶为空),最坏情况下总状态数为213,直接进行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;
} 
Category: USACO | Tags: usaco | Read Count: 675

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com