UVA10603倒水问题+隐式图搜索

 1 /*倒水问题UVA10603:
 2 隐式图搜索：
 3 我觉得解决这类问题，有几点很重要：
 4 1、状态的表示（压缩状态表示可以减小空间复杂度）
 5 2、时间复杂度（状态数）的正确评估，你要保证暴力法是可以解决的。换句话说，状态很快会被填满
 6 3、编码的细心程度（废话，不过算法简单的话，对编码的要求自然就高了很多）
 7 显然，这道题的状态上限是200*200，因为a'+b'+c'=c也可以简化状态的表示
 8 */
 9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include <math.h>
13 #include <ctype.h>
14 #include <string>
15 #include <iostream>
16 #include <sstream>
17 #include <vector>
18 #include <queue>
19 #include <stack>
20 #include <map>
21 #include <list>
22 #include <set>
23 #include <algorithm>
24 #define INF 1e10
25 #define maxn 200+10
26 
27 using namespace std;
28 int a,b,c,d;
29 int dt[maxn];//d==i是对应的最少倒水量
30 bool mark[maxn][maxn];//记录状态的节点，以a和b的水量就可以了
31 struct Node
32 {
33     int a,b,c,t;//t是总倒水量
34 //    Node(){a=0,b=0,c=0,t=0;}
35 };
36 void solve()
37 {
38     memset(mark,0,sizeof(mark));
39     for(int i=0;i<=d;i++) dt[i]=INF;
40     queue<Node>Q;
41     Q.push((Node){0,0,c,0});
42     while(!Q.empty())
43     {
44         Node no=Q.front();
45         Q.pop();
46         int a1=no.a,b1=no.b,c1=no.c,t1=no.t;
47         dt[a1]=min(dt[a1],t1);dt[b1]=min(dt[b1],t1);dt[c1]=min(dt[c1],t1);
48         int na,nb,nc,nt;
49         if (mark[a1][b1]) continue;
50         mark[a1][b1]=true;
51         //a->b
52         int rb=b-b1;
53         if (a1>=rb) {nb=b;na=a1-rb;nt=t1+rb; Q.push((Node){na,nb,c1,nt});}
54         else if (a1<rb){nb=b1+a1;na=0;nt=t1+a1; Q.push((Node){na,nb,c1,nt});}
55         //b->a
56         int ra=a-a1;
57         if (b1>=ra) {na=a;nb=b1-ra;nt=t1+ra; Q.push((Node){na,nb,c1,nt});}
58         else if (b1<ra){na=a1+b1;nb=0;nt=t1+b1; Q.push((Node){na,nb,c1,nt});}
59         //a->c
60         int rc=c-c1;
61         if (a1>=rc) {nc=c;na=a1-rc;nt=t1+rc; Q.push((Node){na,b1,nc,nt});}
62         else if (a1<rc){nc=c1+a1;na=0;nt=t1+a1; Q.push((Node){na,b1,nc,nt});}
63         //c->a
64         ra=a-a1;
65         if (c1>=ra) {na=a;nc=c1-ra;nt=t1+ra; Q.push((Node){na,b1,nc,nt});}
66         else if (c1<ra){na=a1+c1;nc=0;nt=t1+c1; Q.push((Node){na,b1,nc,nt});}
67         //b->c
68         rc=c-c1;
69         if (b1>=rc) {nc=c;nb=b1-rc;nt=t1+rc; Q.push((Node){a1,nb,nc,nt});}
70         else if (b1<rc){nc=c1+b1;nb=0;nt=t1+b1; Q.push((Node){a1,nb,nc,nt});}
71         //c->b
72         rb=b-b1;
73         if (c1>=rb) {nb=b;nc=c1-rb;nt=t1+rb; Q.push((Node){a1,nb,nc,nt});}
74         else if (c1<rb){nb=b1+c1;nc=0;nt=t1+c1; Q.push((Node){a1,nb,nc,nt});}
75     }
76     return;
77 }
78 int t;
79 int main()
80 {
81     cin>>t;
82     while(t--){
83         scanf("%d%d%d%d",&a,&b,&c,&d);
84         solve();
85         int maxd=-1;
86         for(int i=d;i>=0;i--)
87         if (dt[i]<INF) {maxd=max(maxd,i);break;}
88         cout<<dt[maxd]<<" "<<maxd<<endl;
89     }
90     return 0;
91 }