POJ 3414 Pots(模拟bfs+路径记录)

小咪咪 2024-02-17 19:08 26阅读 0赞

题意：
    给出两个容积分别为 a 和 b 的pot，按照以下三种操作方式，求出能否在一定步数后，使者两个pot的其中一个的水量为c。
          1.FILL(i)：将i pot倒满水。
          2.DROP(i)：将i pot倒空水。
          3.POUR(i,j)： 将i pot的水倒到j pot上，直至要么i pot为空，要么j pot为满。

思路：bfs求解，六种状态，并记录路径

AC代码如下:

#include<cstdio>
    #include<queue>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=100+5;
    struct node{
    	int a,b;
    	int type; //1(FILL(1))、2（FILL(2)）、3（DROP(1)）、4（DROP(2)）、5(POUR(1,2)) 、6（POUR(2,1)） 
    	node(int a=0,int b=0,int type=0):a(a),b(b),type(type){}
    }ns;
    int d[maxn][maxn];
    node path[maxn][maxn];     //保存路径 
    int A,B,C;
    void print(node nd){
    	vector<node>vec;
    	while(true){
    		vec.push_back(nd);
    		if(d[nd.a][nd.b]==0)break ;
    		nd=path[nd.a][nd.b];	
    	}
    	for(int i=vec.size()-1;i>=0;i--){
    		node nt=vec[i];
    		switch(nt.type){
    			case 1:printf("FILL(1)\n");break;
    			case 2:printf("FILL(2)\n");break;
    			case 3:printf("DROP(1)\n");break;
    			case 4:printf("DROP(2)\n");break;
    			case 5:printf("POUR(1,2)\n");break;
    			case 6:printf("POUR(2,1)\n");
    		}
    	}
    }
    void bfs(){
    	memset(d,-1,sizeof(d));
    	queue<node>q;
    	q.push(ns);
    	d[ns.a][ns.b]=0;
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(u.a==C||u.b==C){
    			printf("%d\n",d[u.a][u.b]);
    			print(u);
    			return ;
    		}
    		for(int i=1;i<=6;i++){      //六种状态的判定 
    			node v;
    			if(i==1){   //FILL(1)
    				v.a=A;
    				v.b=u.b;
    				v.type=1;
    			}
    			else if(i==2){  // FILL(2)
    				v.b=B;
    				v.a=u.a;
    				v.type=2;
    			}
    			else if(i==3){ //DROP(1)
    				v.a=0;
    				v.b=u.b;
    				v.type=3;
    			}
    			else if(i==4){  //DROP(2)
    				v.b=0;
    				v.a=u.a;
    				v.type=4;
    			}
    			else if(i==5){       //POUR(1,2)
    				int min1=min(u.a,B-u.b);
    				v.a=u.a-min1;
    				v.b=u.b+min1;
    				v.type=5;
    			}
    			else {      //POUR(2,1)
    				int min1=min(u.b,A-u.a);
    				v.b=u.b-min1;
    				v.a=u.a+min1;
    				v.type=6;
    			}
    			if(d[v.a][v.b]==-1){
    				q.push(v);
    				d[v.a][v.b]=d[u.a][u.b]+1;
    				path[v.a][v.b]=u;
    			}
    		}
    	}
    	printf("impossible\n");
    }
    int main(){
    	while(scanf("%d%d%d",&A,&B,&C)==3){
         bfs();	
    	}
    	return 0;
    }