http://poj.org/problem?id=3414
1 #include2 #include 3 #include 4 #include 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 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