07-31 02:00 阅读 116

H - Pots

题目大意

输入两个容器的容量A,B，一开始让两个容器为空，然后给你对这两个容器的6种操作，让你用这6种操作最终使得A或B容器里的水最终达到C，让你输出需要倒水的次数，以及从一开始到后来得到结果的路径。（要求C的大小在A和B之间）

思路

每次可以执行六种操作{"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"}，最后要求你用最少的次数去让某个容器里的水达到C,显然可以用BFS去模拟这六种操作，直到可以使某个容器V==C，这道题还需要你去打印操作步骤，我想的是用dfs从终点（a,b) 递归打印到起始状态（0,0）
我用到了两个结构体，第一个结构体来保存

[ 1 ] 某个容器状态为 x,y 时的父亲状态
[ 2 ] （0,0）到（x,y)的最小步数（我只在第一次更新v[x][y]时去存step，step一定是最小的

[ 3 ] 执行的操作编号

struct node{
 int a; int b; int step; int operation;
 }v[110][110];

第二个结构体，是入队实际存储的某个状态（x,y)

struct nude{
 int x,y;//实际存储的 
 }now,front;

代码

#include <iostream>#include <algorithm>#include <cstring>#define endl '\n'#include <queue>using namespace std;char ch[10][10]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};struct node{
	int a;	int b;	int step;	int operation;
}v[110][110];int tar,A,B;struct nude{
	int x,y;
}now,front;void dfs(int x,int y){	if(x==0&&y==0)
	{		return ;
	}
    dfs(v[x][y].a,v[x][y].b);//一直递归打印，直到（0，0）
    
	printf("%s\n",ch[ v[x][y].operation]);
	
}void bfs(){
	now.x=0;
	now.y=0;	queue<nude>q;
	v[0][0].step=1;
	q.push(now);	while(!q.empty())
	{
		front=q.front();
		q.pop();		if(front.x==tar||front.y==tar)
		{			//开始打印
			//总步数
			printf("%d\n",v[front.x][front.y].step-1); //我把首节点step标为1，此时要减去
			dfs(front.x,front.y); 
			return;
		}		
		//总共有六种操作,更新存储状态 
		for(int i=1;i<=6;i++)
		{   now=front;		  	if(i==1)
		  	{
		  	  now.x=A;	
			}			else if(i==2)
			{
				now.y=B;
			}			else if(i==3)
			{
				now.x=0;
			}			else if(i==4)
			{
				now.y=0;
			}			else if(i==5)//把A倒在B里，两种情况
			{				if(now.x+now.y<=B)
				{	now.y=now.x+now.y;
					now.x=0;
					
				 } 
				 else
				 {
				 	now.x=now.x-(B-now.y);
				 	now.y=B;
				 }
			} 
			else   //同理 
			{				if(now.x+now.y<=A)
				{	now.x=now.x+now.y;
					now.y=0;
					
				 } 
				 else
				 {
				 	now.y=now.y-(A-now.x);
				 	now.x=A;
				 }
			}			//如果改点未走过，说明这次 (a,b)是最小步数 
			if(v[now.x][now.y].step==0)
			{				//push
				
				v[now.x][now.y].a=front.x;
				v[now.x][now.y].b=front.y;
				v[now.x][now.y].operation=i-1;
				v[now.x][now.y].step=v[front.x][front.y].step+1;
				q.push(now);
			}
		} 
	}	printf("impossible\n");
}int main(){   while(cin>>A>>B>>tar)
   {memset(v,0,sizeof(v));
   	bfs();
   }   return 0;
}

分类: 搜索

来源https://www.cnblogs.com/Xiaomostream/p/15083259.html