HDU - 1495 非常可乐

 1 #include<iostream>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 struct Status{
 7     int v[3];
 8     int step;
 9 };
10 
11 int S,N,M;
12 int min_step=9999;
13 int pre[101][101][101]={0}; //之前到达过的状态
14 queue<Status> q; //BFS队列
15 
16 int main(){
17     cin >>S>>N>>M;
18     while(S!=0){
19         if(S%2!=0){
20             cout <<"NO"<<endl;
21         }else{
22             bool succ=false;
23             int V[3]; //用于存储S,N,M
24             V[0]=S;V[1]=N;V[2]=M;
25             Status begin;
26             begin.v[0]=S;begin.v[1]=0;begin.v[2]=0;begin.step=0;
27             pre[begin.v[0]][begin.v[1]][begin.v[2]]=1;
28             q.push(begin);
29             while(!q.empty()){
30                 Status s=q.front();q.pop();
31                 //检查是否有两个杯子的液体体积为总体积的一半
32                 if((s.v[0]==S/2&&s.v[1]==S/2)||(s.v[0]==S/2&&s.v[2]==S/2)||(s.v[1]==S/2&&s.v[2]==S/2)){
33                     if(s.step<min_step){
34                         min_step=s.step;
35                     }
36                     succ=true;
37                     continue;
38                 }
39                 for(int i=0;i<3;i++){
40                     if(s.v[i]>0){
41                         int vv[2];
42                         vv[0]=0;vv[1]=2;
43                         if(i==0){
44                             vv[0]=1;vv[1]=2;
45                         }else if(i==2){
46                             vv[0]=0;vv[1]=1;
47                         }
48                         for(int j=0;j<2;j++){
49                             Status ss=s;
50                             if(ss.v[vv[j]]<V[vv[j]]){
51                                 int sub=V[vv[j]]-ss.v[vv[j]];
52                                 if(sub>=ss.v[i]){
53                                     ss.v[vv[j]]+=ss.v[i];
54                                     ss.v[i]=0;
55                                 }else{
56                                     ss.v[i]-=sub;
57                                     ss.v[vv[j]]=V[vv[j]];
58                                 }
59                                 ss.step++;
60                                 if(pre[ss.v[0]][ss.v[1]][ss.v[2]]==0){
61                                     pre[ss.v[0]][ss.v[1]][ss.v[2]]=1;
62                                     q.push(ss);
63                                 }
64                             }
65                         }
66                     }
67                 }
68             }
69             if(!succ){
70                 cout <<"NO"<<endl;
71             }else{
72                 cout <<min_step<<endl;
73             }
74             while(!q.empty()){
75                 q.pop();
76             }
77         }
78         min_step=9999;
79         memset(pre,0,sizeof(pre));
80         cin >>S>>N>>M;
81     }
82     system("pause");
83     return 0;
84 }