首页 > USACO题解 > USACO Mother’s Milk|DFS

USACO Mother’s Milk|DFS

USACO Mother's Milk以前在POJ上面看到过类似的题目,就是搜索所有可能的状态。对于每一个状态都可能存在6中转换:A->B, A->C; B->A, B->C; C->A, C->B,当然只能选择其中的一种。搜索其中的每一种状态即可。属于简单型的DFS。可以用一个20×20×20的数组来判重。

/*
	ID:stackex1
	LANG:C++
	PROG:milk3
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
bool state[21][21][21] = {0};
bool flag[21] = {0};
int path[21] = {0};
int idx = 0, vol[3];
 
void DFS(int a, int b, int c)
{
	if(state[a][b][c]) return ;
	state[a][b][c] = true;
	if(a == 0 && !flag[c])
	{
		flag[c] = true;
		path[idx++] = c;
	}
	//A->B
	if(a + b <= vol[1]) DFS(0, a+b, c);
	else DFS(a-(vol[1]-b), vol[1], c);
	//A->C
	if(a + c <= vol[2]) DFS(0, b, a+c);
	else DFS(a-(vol[2]-c), b, vol[2]);
	//B->A
	if(a + b <= vol[0]) DFS(a+b, 0, c);
	else DFS(vol[0], b-(vol[0]-a), c);
	//B->C
	if(c + b <= vol[2]) DFS(a, 0, c+b);
	else DFS(a, b-(vol[2]-c), vol[2]);
	//C->A
	if(c + a <= vol[0]) DFS(c+a, b, 0);
	else DFS(vol[0], b, c-(vol[0]-a));
	//C->B
	if(c + b <= vol[1]) DFS(a, b+c, 0);
	else DFS(a, vol[1], c-(vol[1]-b));
 
	return ;
}
 
int main(int argc, char **argv)
{
	FILE *fin = fopen("milk3.in", "r");
	FILE *fout = fopen("milk3.out", "w");
	int i, n = 3;
	for(i = 0; i < n; ++i)
		fscanf(fin, "%d", &vol[i]);
	DFS(0, 0, vol[2]);
	sort(path, path+idx);
	for(i = 0; i < idx-1; ++i)
		fprintf(fout, "%d ", path[i]);
	fprintf(fout, "%d\n", path[i]);
	fclose(fin);
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Mother’s Milk|DFS
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: ,
  1. 2010年12月2日23:18 | #1

    速度很快啊.这题判重可以用用两维的数组的。

    [回复]

  2. 2010年12月3日12:07 | #2

    @Klion26
    是吧 是把A+B的和以及C记为一种状态

    [回复]