计蒜客无脑博士的试管们（bfs+模拟）

布满荆棘的人生 2024-02-17 22:14 6阅读 0赞

无脑博士有三个容量分别是 A,B,C 升的试管，A,B,CA,B,C 分别是三个从 1 到 20 的整数，最初，A 和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。

写一个程序去帮助无脑博士找出当A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。

#### 输入格式 ####

输入包括一行，为空格分隔开的三个数，分别为整数 A,B,CA,B,C。

#### 输出格式 ####

输出包括一行，升序地列出当A 试管是空的时候，CC 试管溶液所剩量的所有可能性。

##### 样例输入 #####

2 5 10

##### 样例输出 #####

5 6 7 8 9 10

分析：bfs求解，每种状态三个杯子A,B,C中的水n,m,s，六种相互倒水状态，（A->B,A-C;B->A,B->C;C->A,C->B），每次从要倒水的杯子（剩余水量a）和要倒入水的杯中（剩余容量b）选择一个小者。模拟即可

AC代码：

#include<cstdio>
    #include<cstring>
    #include<set>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=20+2;
    int vis[maxn][maxn];
    struct node{
    	int n,m,s;
    	node(int n=0,int m=0,int s=0):n(n),m(m),s(s){}
    };
    int A,B,C;
    set<int>st;   
     
    void bfs(){
         memset(vis,0,sizeof(vis));
         st.clear();
         queue<node>q;
         q.push(node(0,0,C));
         vis[0][0]=1;
         st.insert(C);
         int Cup[3]={A,B,C};
         
         while(!q.empty()){
         	node u=q.front();
         	q.pop();
         	
         	if(u.n==0){
         		st.insert(u.s);
    		 }
    		 
    		 int a[3];
    		 
    		 for(int i=0;i<3;i++){
    		 	for(int j=0;j<3;j++){
    		        a[0]=u.n,a[1]=u.m,a[2]=u.s;
    		 		if(i!=j){
    		 			int t=min(a[i],Cup[j]-a[j]);
    		 			a[i]-=t;
    		 			a[j]+=t;
    		 			node v = node(a[0],a[1],a[2]);
    		 			if(!vis[v.n][v.m]){
    		 				vis[v.n][v.m]=1;
    		 				q.push(v);
    					 }
    				 }
    			 }
    		 }
    	 }
    }
    
    int main(){
    	while(scanf("%d%d%d",&A,&B,&C)==3){
    		bfs();
    		set<int>::iterator iter=st.begin();
    		printf("%d",*iter);
    		iter++;
    		for(;iter!=st.end();iter++){
    			printf(" %d",*iter);
    		}
    		printf("\n");
    	}	
    	return 0;
    }