三個水杯
時間限制：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 這題和前兩天寫的 poj 中jugs那道題思路一樣，用 隊列 加上 搜尋 搞定
這是本題OJ上的最優代碼：---好短1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 6 using namespace std; 7 8 int va, vb, vc, ta, tb, tc; 9 bool visit[205][205][205]; 10 struct state 11 { 12 int a; 13 int b; 14 int c; 15 int step; 16 }; 17 18 inline bool check(state t) 19 { 20 if(t.a == ta && t.b == tb && t.c == tc) 21 return true; 22 return false; 23 } 24 25 int BFS(int sa, int sb, int sc) 26 { 27 queue <state> q; 28 state t1, t2; 29 t1.a = sa; 30 t1.b = sb; 31 t1.c = sc; 32 t1.step = 0; 33 q.push(t1); 34 while(!q.empty()) 35 { 36 t1 = q.front(); 37 q.pop(); 38 if(t1.b != vb && t1.a) // pour va to vb 39 { 40 if(t1.a <= vb - t1.b) 41 { 42 t2.a = 0; 43 t2.b = t1.b + t1.a; 44 t2.c = t1.c; 45 } 46 else 47 { 48 t2.a = t1.a - (vb - t1.b); 49 t2.b = vb; 50 t2.c = t1.c; 51 } 52 if(!visit[t2.a][t2.b][t2.c]) 53 { 54 t2.step = t1.step + 1; 55 if(check(t2)) 56 return t2.step; 57 visit[t2.a][t2.b][t2.c] = true; 58 q.push(t2); 59 } 60 } 61 if(t1.c != vc && t1.a) // pour va to vc 62 { 63 if(t1.a <= vc - t1.c) 64 { 65 t2.a = 0; 66 t2.b = t1.b; 67 t2.c = t1.c + t1.a; 68 } 69 else 70 { 71 t2.a = t1.a - (vc - t1.c); 72 t2.b = t1.b; 73 t2.c = vc; 74 } 75 if(!visit[t2.a][t2.b][t2.c]) 76 { 77 t2.step = t1.step + 1; 78 if(check(t2)) 79 return t2.step; 80 visit[t2.a][t2.b][t2.c] = true; 81 q.push(t2); 82 } 83 } 84 if(t1.a != va && t1.b) // pour vb to va 85 { 86 if(t1.b <= va - t1.a) 87 { 88 t2.b = 0; 89 t2.a = t1.b + t1.a; 90 t2.c = t1.c; 91 } 92 else 93 { 94 t2.b = t1.b - (va - t1.a); 95 t2.a = va; 96 t2.c = t1.c; 97 } 98 if(!visit[t2.a][t2.b][t2.c]) 99 { 100 t2.step = t1.step + 1; 101 if(check(t2)) 102 return t2.step; 103 visit[t2.a][t2.b][t2.c] = true; 104 q.push(t2); 105 } 106 } 107 if(t1.a != va && t1.b) // pour vb to vc 108 { 109 if(t1.b <= vc - t1.c) 110 { 111 t2.b = 0; 112 t2.a = t1.a; 113 t2.c = t1.b + t1.c; 114 } 115 else 116 { 117 t2.b = t1.b - (vc - t1.c); 118 t2.a = t1.a; 119 t2.c = vc; 120 } 121 if(!visit[t2.a][t2.b][t2.c]) 122 { 123 t2.step = t1.step + 1; 124 if(check(t2)) 125 return t2.step; 126 visit[t2.a][t2.b][t2.c] = true; 127 q.push(t2); 128 } 129 } 130 if(t1.a != va && t1.c) // pour vc to va 131 { 132 if(t1.c <= va - t1.a) 133 { 134 t2.c = 0; 135 t2.a = t1.a + t1.c; 136 t2.b = t1.b ; 137 } 138 else 139 { 140 t2.c = t1.c - (va - t1.a); 141 t2.a = va; 142 t2.b = t1.b; 143 } 144 if(!visit[t2.a][t2.b][t2.c]) 145 { 146 t2.step = t1.step + 1; 147 if(check(t2)) 148 return t2.step; 149 visit[t2.a][t2.b][t2.c] = true; 150 q.push(t2); 151 } 152 } 153 if(t1.b != vb && t1.c) // pour vc to vb 154 { 155 if(t1.c <= vb - t1.b) 156 { 157 t2.c = 0; 158 t2.b = t1.b + t1.c; 159 t2.a = t1.a ; 160 } 161 else 162 { 163 t2.c = t1.c - (vb - t1.b); 164 t2.b = vb; 165 t2.a = t1.a; 166 } 167 if(!visit[t2.a][t2.b][t2.c]) 168 { 169 t2.step = t1.step + 1; 170 if(check(t2)) 171 return t2.step; 172 visit[t2.a][t2.b][t2.c] = true; 173 q.push(t2); 174 } 175 } 176 } 177 return -1; 178 } 179 180 int main() 181 { 182 int T; 183 scanf("%d", &T); 184 while(T--) 185 { 186 memset(visit, false, sizeof(visit)); 187 scanf("%d %d %d", &va, &vb, &vc); 188 scanf("%d %d %d", &ta, &tb, &tc); 189 if(va == ta && 0 == tb && 0 == tc) 190 { 191 printf("0\n"); 192 continue; 193 } 194 visit[va][0][0] = true; 195 printf("%d\n", BFS(va, 0, 0)); 196 } 197 //system("pause"); 198 return 0; 199 }1 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<bitset> 7 using namespace std; 8 #define CLR(arr,val) memset(arr,val,sizeof(arr)) 9 bitset<1000000> Hash; 10 const int MAX_STEP=100000; 11 int WQ[MAX_STEP][4],Goal[3],Cap[3],goalval; 12 int head=0,tail=0; 13 void movw(int numfrom,int numto,int other) 14 { 15 int total=WQ[head][numfrom]+WQ[head][numto]; 16 WQ[tail][other]=WQ[head][other]; 17 WQ[tail][3]=WQ[head][3]+1; 18 if(total>Cap[numto]) 19 { 20 WQ[tail][numfrom]=total-Cap[numto]; 21 WQ[tail][numto]=Cap[numto]; 22 } 23 else 24 { 25 WQ[tail][numfrom]=0; 26 WQ[tail][numto]=total; 27 } 28 int hashval=WQ[tail][0]*10000+WQ[tail][1]*100+WQ[tail][2]; 29 if(hashval==goalval) throw WQ[head][3]+1; 30 if(WQ[head][numfrom]!=0 && !Hash[hashval]) 31 { 32 Hash[hashval]=true; 33 if(++tail==MAX_STEP) tail=0; 34 } 35 } 36 int main() 37 { 38 int t; 39 scanf("%d",&t); 40 while(t--) 41 { 42 Hash.reset(); 43 scanf("%d%d%d%d%d%d",&Cap[0],&Cap[1],&Cap[2],&Goal[0],&Goal[1],&Goal[2]); 44 head=0,tail=0,goalval=Goal[0]*10000+Goal[1]*100+Goal[2]; 45 if(Goal[1]==0 && Goal[2]==0 && Goal[0]==Cap[0]) {puts("0");continue;} 46 WQ[tail][0]=Cap[0];WQ[tail][1]=0;WQ[tail][2]=0;WQ[tail][3]=0; 47 ++tail; 48 try{ 49 while(head!=tail) 50 { 51 movw(0,1,2);movw(1,2,0);movw(0,2,1);movw(1,0,2);movw(2,1,0);movw(2,0,1); 52 if(++head==MAX_STEP) head=0; 53 } 54 puts("-1"); 55 }catch(int step) 56 { 57 printf("%d\n",step); 58 } 59 } 60 }