neoevoke » [usaco] 1.4 Mother's Milk

[usaco] 1.4 Mother's Milk - usaco

2009.08.08 23:02 neoevoke Edit

다이하드 3에 나오는 3갤런 5갤런 물통으로 4갤런 만들기 이런거랑 좀 비슷한 문제이다.

a,b,c갤런의 물통이 있고 c갤런의 물통에만 물이 가득차 있을 때 a갤런의 물통이 비었을 때 c갤런의 물통에는 몇갤런이 남아있을 수 있을까 하는 문제이다.

주어진 제약조건에 맞춰서 dfs로 다 돌리면 된다.

/*
ID: neoevok1
PROG: milk3
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> ret;
bool visited[21][21][21];

int a,b,c;
void dfs(int aa,int bb, int cc)
{
	if(aa<0||bb<0||cc<0||aa>a||bb>b||cc>c)
		return;
	if(visited[aa][bb][cc]) return;

visited[aa][bb][cc]=1;
	if(aa>0)
	{
		if(aa-(b-bb)>0)
			dfs(aa-(b-bb),b,cc);
		else
			dfs(0,bb+aa,cc);

if(aa-(c-cc)>0)
			dfs(aa-(c-cc),bb,c);
		else
			dfs(0,bb,cc+aa);

}

if(bb>0)
	{
		if(bb-(a-aa)>0)
			dfs(a,bb-(a-aa),cc);
		else
			dfs(aa+bb,0,cc);

if(bb-(c-cc)>0)

dfs(aa,bb-(c-cc),c);	
		else
			dfs(aa,0,cc+bb);	
	}

if(cc>0)
	{
		if(cc-(a-aa)>0)
			dfs(a,bb,cc-(a-aa));
		else
			dfs(aa+cc,bb,0);

if(cc-(b-bb)>0)
			dfs(aa,b,cc-(b-bb));
		else
			dfs(aa,bb+cc,0);			
	}
}

int main() {
    ofstream fout ("milk3.out");
    ifstream fin ("milk3.in");

fin >> a >> b >> c;

for(int i=0;i<21;i++)
	for(int j=0;j<21;j++)
	for(int k=0;k<21;k++)
	visited[i][j][k]=0;

dfs(0,0,c);

for(int j=0;j<=20;j++)
	for(int k=0;k<=20;k++)
		if(visited[0][j][k])
		{
			ret.push_back(k);
		}

sort(ret.begin(), ret.end());
	vector<int>::iterator itend = unique(ret.begin(), ret.end());
	ret.resize(itend-ret.begin());
	if(ret.size()>0)
	{
		fout << ret[0] ;
		for(int i=1;i<(int)ret.size();i++)
			fout << " " << ret[i];
		fout << endl;
	}

return 0;
}

Perfect balanced KDTree * Pacific Northwestsern Regional 2008

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329395/be9/trackback

Comments 0

Leave Comments

neoevoke난 전설 같은건 믿지 않아

[usaco] 1.4 Mother's Milk - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag