nyoj 21 三个水杯（模拟bfs）

落日映苍穹つ 2024-02-18 17:49 18阅读 0赞

### 三个水杯 ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 4

描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0<N<50)表示N组测试数据  
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。  
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

2
    6 3 1
    4 1 1
    9 3 2
    7 1 1

样例输出

3
    -1

思路：每次循环有六种状态（三个水杯之间相互倒水），每次从倒水的杯子能到出的最大容量a\[i\] 和倒入水的杯子能装最大容量v\[j\]-a\[j\]中选出小者，然后在看d\[a\[0\]\]\[a\[1\]\]\[a\[2\]\]这种状态是否被访问了，没有访问则加入队列，访问过了就不管了。

AC代码：

#include<cstdio>
    #include<queue>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn = 100 + 2;
    int d[maxn][maxn][maxn];
    struct node{
    	int cnt; //到目前的状态，倒水的次数 
    	int a,b,c;  //三个杯子当前装的水容量 
    	node(int a,int b,int c,int cnt):a(a),b(b),c(c),cnt(cnt){}
    	node(){}
    	bool operator < (const node& nd)const {   //cnt值小者 先出队列 
    	     return this->cnt > nd.cnt;
    	}
    } ns,ne;
    
    int v[3];//杯子容量 
    
    void bfs(){
    	memset(d,0,sizeof(d));
    	d[ns.a][ns.b][ns.c] = 1;  //此状态被访问过了 
    	priority_queue<node> q;
    	q.push(ns);
    	while(!q.empty()){
    		node u = q.top(); q.pop();
    		if(u.a == ne.a && u.b == ne.b && u.c == ne.c){
    			printf("%d\n",u.cnt);
    			return ;
    		}
    
    		for(int i = 0; i < 3; i++){	//将水倒出的杯子 
    			for(int j = 0; j < 3; j++){  //将水倒入的杯子 
    				int a[3]={u.a,u.b,u.c};	
    				if(i != j){
    				   int Min = min(a[i],v[j]-a[j]);  //从倒出水容量为a[i]的杯子和倒入能装容量v[j]-a[j]的杯子中选择小者 
    				   a[i] -= Min;
    				   a[j] += Min;					
    				if(!d[a[0]][a[1]][a[2]]){
    					d[a[0]][a[1]][a[2]] = 1;
    					q.push(node(a[0],a[1],a[2],u.cnt + 1));
    				}
    			  }
    			}
    		} 
    	}
    	
    	printf("-1\n");
    }
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	while(n--){
    		scanf("%d%d%d",&v[0],&v[1],&v[2]);  //杯子容量 
    		scanf("%d%d%d",&ne.a,&ne.b,&ne.c);  //目标状态 
    		ns.a = v[0] ,ns.b = 0, ns.c = 0, ns.cnt = 0;
    		if((ne.a + ne.b + ne.c) > v[0]){
    			printf("-1\n"); continue;
    		}
    		bfs();
    	} 
    	return 0;
    }