POJ 3414 pots （未解决）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <queue>
  4 #include <cstring>
  5 
  6 using namespace std;
  7 
  8 struct node{
  9     int first;
 10     int second;
 11     int opera[1000];
 12     int cou;
 13 };
 14 queue<node> que;
 15 int vis[105][105];
 16 
 17 //opera数组数据意义
 18 //fill(1)   110----120
 19 //drop(1)   210----220
 20 //pour(1,2) 312----321
 21 //三位数分别表示操作，第一个参数，第二个参数
 22 
 23 node bfs(int a,int b,int c){
 24     node ff;
 25     ff.first=0;
 26     ff.second=0;
 27     ff.cou=0;
 28     que.push(ff);
 29     node t;
 30     memset(vis,0,sizeof(vis));
 31     while(!que.empty()){
 32         node f=que.front();
 33         que.pop();
 34         if(f.first==c||f.second==c){
 35             return f;
 36         }
 37         t=f;
 38         t.first=a;
 39         t.opera[t.cou++]=110;
 40         if(vis[t.first][t.second]!=1){
 41             que.push(t);
 42         }
 43         vis[t.first][t.second]=1;
 44 
 45         t=f;
 46         t.first=0;
 47         t.opera[t.cou++]=210;
 48         if(vis[t.first][t.second]!=1){
 49             que.push(t);
 50         }
 51         vis[t.first][t.second]=1;
 52 
 53         t=f;
 54         int l=b-t.second;
 55         if(t.first>=l){
 56             t.second=b;
 57             t.first-=l;
 58         }else{
 59             t.second+=t.first;
 60             t.first=0;
 61         }
 62         t.opera[t.cou++]=312;
 63         if(vis[t.first][t.second]!=1){
 64             que.push(t);
 65         }
 66         vis[t.first][t.second]=1;
 67 
 68         t=f;
 69         t.second=b;
 70         t.opera[t.cou++]=120;
 71         if(vis[t.first][t.second]!=1){
 72             que.push(t);
 73         }
 74         vis[t.first][t.second]=1;
 75 
 76         t=f;
 77         t.second=0;
 78         t.opera[t.cou++]=220;
 79         if(vis[t.first][t.second]!=1){
 80             que.push(t);
 81         }
 82         vis[t.first][t.second]=1;
 83 
 84         t=f;
 85         l=a-t.first;
 86         if(t.second>=l){
 87             t.first=a;
 88             t.second-=l;
 89         }else{
 90             t.first+=t.second;
 91             t.second=0;
 92         }
 93         que.push(t);
 94         vis[t.first][t.second]=1;
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int a,b,c;
101     while(~scanf("%d %d %d",&a,&b,&c)){
102         if(a==b&&b==c){
103             printf("1\n");
104             printf("FILL(1)\n");
105             continue;
106         }else if(a==b&&b!=c||c>a&&c>b){
107             printf("impossible\n");
108             continue;
109         }
110         node ans=bfs(a,b,c);
111         printf("%d\n",ans.cou);
112         for(int i=0;i<ans.cou;i++){
113             int baiwei=ans.opera[i]%100;
114             int shiwei=ans.opera[i]/10%10;
115             int gewei=ans.opera[i]%10;
116             if(baiwei==1){
117                 if(shiwei==1){
118                     printf("FILL(%d)\n",1);
119                 }else{
120                     printf("FILL(%d)\n",2);
121                 }
122             }else if(baiwei==2){
123                 if(shiwei==1){
124                     printf("DROP(%d)\n",1);
125                 }else{
126                     printf("DROP(%d)\n",2);
127                 }
128             }else if(gewei==3){
129                 printf("POUR(%d,%d)\n",shiwei,gewei);
130             }
131         }
132     }
133     return 0;
134 }