POJ 3414 Pots

Doubi Gao3 posted @ 2013年12月29日 14:36 in acm with tags BFS , 963 阅读

好久没发关于ACM的文章了,以前的博客几个月没用了。今天随便水了一题,顺便发第一篇在这博客上的ACM的文章。

 

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

//fill 1 0
//drop 1 1
//fill 2 2
//drop 2 3
//pour(1, 2) 4
//pour(2, 1) 5

struct node
{
	int v[2];
	string step;
	int ans;
};

int A, B, C;

bool vis[110][110];

node bfs()
{
	memset(vis, 0, sizeof(vis));
	
	node cur, next;
	cur.v[0] = 0, cur.v[1] = 0, cur.step = "", cur.ans = 0;
	vis[0][0] = 1;
	queue<node> Q;
	
	Q.push(cur);
	
	while(!Q.empty())
	{
		cur = Q.front(); Q.pop();
		
		int a = cur.v[0], b = cur.v[1];
		if(a == C || b == C) return cur;
		
		if(a != A && !vis[A][b]) //fill 1
		{
			next = cur;
			next.v[0] = A;
			vis[A][b] = 1;
			next.step += '0', next.ans++;
			Q.push(next);
		}
		
		if(a > 0 && !vis[0][b]) //drop 1
		{
			next = cur;
			next.v[0] = 0;
			vis[0][b] = 1;
			next.step += '1', next.ans++;
			Q.push(next);
		}
		
		if(b != B && !vis[a][B]) //fill 2 
		{
			next = cur;
			next.v[1] = B;
			vis[a][B] = 1;
			next.step += '2', next.ans++;
			Q.push(next);
		}
		
		if(b > 0 && !vis[a][0]) //drop 2
		{
			next = cur;
			next.v[1] = 0;
			vis[a][0] = 1;
			next.step += '3', next.ans++;
			Q.push(next);	
		}
		
		if(b != B && a+b < B && !vis[0][a+b]) //pour(1, 2)
		{
			next = cur;
			next.v[0] = 0, next.v[1] = a+b;
			vis[0][a+b] = 1;
			next.step += '4', next.ans++;
			Q.push(next);
		}
		if(b != B && a+b > B && !vis[a-B+b][B])
		{
			next = cur;
			next.v[0] = a-B+b, next.v[1] = B;
			vis[a-B+b][B] = 1;
			next.step += '4', next.ans++;
			Q.push(next);
		}
		
		if(a != A && a+b < A && !vis[a+b][0]) //pour(2, 1)
		{
			next = cur;
			next.v[0] = a+b, next.v[1] = 0;
			vis[a+b][0] = 1;
			next.step += '5', next.ans++;
			Q.push(next);
		}
		if(a != A && a+b > A && !vis[A][b-A+a])
		{
			next = cur;
			next.v[0] = A, next.v[1] = b-A+a;
			vis[A][b-A+a] = 1;
			next.step += '5', next.ans++;
			Q.push(next);
		}
	}
	
	node b;
	b.ans = -1;
	return b;
}

void print(node a)
{
	int n = a.step.length();
	
	printf("%d\n", a.ans);
	for(int i = 0; i < n; i++)
	{
		char c = a.step[i];
		switch(c)
		{
			case '0': printf("FILL(1)\n"); break;
			case '1': printf("DROP(1)\n"); break;
			case '2': printf("FILL(2)\n"); break;
			case '3': printf("DROP(2)\n"); break;
			case '4': printf("POUR(1,2)\n"); break;
			case '5': printf("POUR(2,1)\n"); break;
			default: break;
		}
	}
}

int main()
{
	while(~scanf("%d%d%d", &A, &B, &C))
	{
		node ans = bfs();
		if(ans.ans == -1) { printf("impossible\n"); continue ; }
		print(ans);
	}
	return 0;
}

登录 *


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