UVA 10603 - Fill BFS~

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1544&mosmsg=Submission+received+with+ID+13026638

题目大意：

有3个没有刻度的水壶，容量分别为a,b,c（均不超过200的正整数）。初始时候前两个水壶空，第三个装满了水。每次可以从一个水壶往另一个水壶倒水，直到其中一个水壶倒空或者另一个水壶倒满。为了使某个水壶恰好有d升水，至少要倒多少升的水？如果无解，则找一个小于且最接近于d的d'代替。

输出要求输出至少倒多少升水和 d(d'）

思路：

把能达到的状态看成图上的点，进行BFS。

然后我用的是优先队列，能保证最少倒的条件。（按当前倒的水量维护好了）

建模确实不太好建。

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int MAXN=200+10;

const int INF=2000000;

bool vis[MAXN][MAXN][MAXN];

int state[3],d,ans;

struct node

{

	int state[3];

	int val;

	node(){}

	node(int aa,int bb,int cc,int dd){ state[0]=aa;state[1]=bb;state[2]=cc;val=dd;}

	bool operator <(const node & x)const

	{

		return val>x.val;

	}

};

void bfs()

{

	memset(vis,0,sizeof(vis));

	priority_queue<node> q;

	q.push(node(0,0,state[2],0));

	vis[0][0][state[2]]=true;

	while(!q.empty())

	{

		node cur=q.top();

		q.pop();

		if(cur.state[0]==d || cur.state[1]==d || cur.state[2]==d)

		{

			ans=cur.val;

			return;

		}

		for(int i=0;i<3;i++)

		{

			for(int j=0;j<3;j++)        //j往i倒水

			{

				if(i==j)	continue;     //不能自己给自己倒水

				if(!cur.state[j])	continue;	//为空不行

				node temp;

				int *t=temp.state;   //用指针优化下可读性  就是说t和temp.state是一个数组

				if(cur.state[j] + cur.state[i] > state[i]) //超过了容量，只能倒满

				{

					t[i]=state[i];

					t[j]=cur.state[j] + cur.state[i] -state[i];

					t[3-i-j]=cur.state[3-i-j];       //3=0+1+2 所以减去代表剩下的那个

					temp.val=cur.val+state[i] - cur.state[i];

				}

				else

				{

					t[i]=cur.state[j] + cur.state[i];

					t[j]=0;

					t[3-i-j]=cur.state[3-i-j];

					temp.val=cur.val+cur.state[j];

				}

				if(!vis[ t[0] ][ t[1] ][ t[2] ])		//没访问过才加入队列

				{

					vis[ t[0] ][ t[1] ][ t[2] ]=true;

					q.push(temp);

				}

			}

		}

	}

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		ans=INF;

		scanf("%d%d%d%d",&state[0],&state[1],&state[2],&d);

		bfs();

		while(ans==INF)

		{

			d--;

			bfs();

		}

		printf("%d %d\n",ans,d);

	}

	return 0;

}

巴特西

UVA 10603 - Fill BFS~

最新文章

热门文章