uva 571 - Jugs

  1  /*
  2  Problem link
  3  Type: Graph - DP
  4  Algorithm: BFS
  5  */
  6  #include <iostream>
  7  #include <cstdio>
  8  #include <cstring>
  9  #include <cmath>
 10  #include <cstdlib>
 11  #include <queue>
 12  #include <vector>
 13  using namespace std;
 14  
 15  const int maxn = 1010;
 16  const int oo = 2000000000;
 17  
 18  class trace
 19  {
 20  public:
 21      int type;
 22      int x;
 23      int y;
 24  
 25      trace() {};
 26      trace(int t, int i, int j): type(t), x(i), y(j) {}
 27  };
 28  
 29  int f[maxn][maxn];
 30  trace pre[maxn][maxn];
 31  queue<int> qx;
 32  queue<int> qy;
 33  vector<string> ans;
 34  int a,b,n;
 35  
 36  int BFS(int x, int y, vector<string> &ans);
 37  
 38  int main()
 39  {
 40      while (!cin.eof())
 41      {
 42          cin >> a >> b >> n;
 43          if (cin.eof()) break;
 44          for (int i=0; i<maxn; i++)
 45              for (int j=0; j<maxn; j++)
 46              {
 47                  f[i][j] = oo;
 48                  pre[i][j] = trace(0,0,0);
 49              }
 50          ans.clear();
 51          while (!qx.empty()) qx.pop();
 52          while (!qy.empty()) qy.pop();
 53          BFS(0,0,ans);
 54          for (int i=ans.size()-1; i>=0; i--) cout << ans[i] << endl;
 55          cout << "success" << endl;
 56      }
 57      return 0;
 58  }
 59  
 60  int BFS(int x, int y, vector<string> &ans)
 61  {
 62      int i,j;
 63      qx.push(x);
 64      qy.push(y);
 65      f[x][y] = 0;
 66      pre[x][y] = trace(-1,0,0);
 67      do
 68      {
 69          if (qx.empty()) break;
 70          i = qx.front();
 71          qx.pop();
 72          j = qy.front();
 73          qy.pop();
 74          if (j==n) break;
 75          if (f[a][j]==oo)
 76          {
 77              f[a][j] = f[i][j]+1;
 78              pre[a][j] = trace(1,i,j);
 79              if (j==n) break;
 80              qx.push(a);
 81              qy.push(j);
 82          }
 83          if (f[i][b]==oo)
 84          {
 85              f[i][b] = f[i][j]+1;
 86              pre[i][b] = trace(2,i,j);
 87              if (j==n) break;
 88              qx.push(i);
 89              qy.push(b);
 90          }
 91          if (f[0][j]==oo)
 92          {
 93              f[0][j] = f[i][j]+1;
 94              pre[0][j] = trace(3,i,j);
 95              if (j==n) break;
 96              qx.push(0);
 97              qy.push(j);
 98          }
 99          if (f[i][0]==oo)
100          {
101              f[i][0] = f[i][j]+1;
102              pre[i][0] = trace(4,i,j);
103              if (j==n) break;
104              qx.push(i);
105              qy.push(0);
106          }
107          if (i>=b-j && f[i-b+j][b]==oo)
108          {
109              f[i-b+j][b] = f[i][j]+1;
110              pre[i-b+j][b] = trace(5,i,j);
111              if (j==n) break;
112              qx.push(i-b+j);
113              qy.push(b);
114          }
115          else if (i<b-j && f[0][i+j]==oo)
116          {
117              f[0][j+i] = f[i][j]+1;
118              pre[0][j+i] = trace(5,i,j);
119              if (j==n) break;
120              qx.push(0);
121              qy.push(i+j);
122          }
123          if (j>=a-i && f[a][j-a+i]==oo)
124          {
125              f[a][j-a+i] = f[i][j]+1;
126              pre[a][j-a+i] = trace(6,i,j);
127              if (j==n) break;
128              qx.push(a);
129              qy.push(j-a+i);
130          }
131          else if (j<a-i && f[i+j][0]==oo)
132          {
133              f[i+j][0] = f[i][j]+1;
134              pre[i+j][0] = trace(6,i,j);
135              if (j==n) break;
136              qx.push(i+j);
137              qy.push(0);
138          }
139      } while(true);
140      int result = oo,ii,jj=n;
141      for (int i=0; i<=a; i++)
142          if (f[i][n]!=oo)
143          {
144              result = f[i][n];
145              ii = i;
146              break;
147          }
148  
149      if (result==oo) return(-1);
150      while (ii!=0 || jj!=0)
151      {
152          int tmpi = ii,
153              tmpj = jj;
154          switch (pre[ii][jj].type)
155          {
156          case 1:
157              {
158                  ans.push_back("fill A");
159                  ii = pre[tmpi][tmpj].x;
160                  jj = pre[tmpi][tmpj].y;
161                  break;
162              }
163          case 2:
164              {
165                  ans.push_back("fill B");
166                  ii = pre[tmpi][tmpj].x;
167                  jj = pre[tmpi][tmpj].y;
168                  break;
169              }
170          case 3:
171              {
172                  ans.push_back("empty A");
173                  ii = pre[tmpi][tmpj].x;
174                  jj = pre[tmpi][tmpj].y;
175                  break;
176              }
177          case 4:
178              {
179                  ans.push_back("empty B");
180                  ii = pre[tmpi][tmpj].x;
181                  jj = pre[tmpi][tmpj].y;
182                  break;
183              }
184          case 5:
185              {
186                  ans.push_back("pour A B");
187                  ii = pre[tmpi][tmpj].x;
188                  jj = pre[tmpi][tmpj].y;
189                  break;
190              }
191          case 6:
192              {
193                  ans.push_back("pour B A");
194                  ii = pre[tmpi][tmpj].x;
195                  jj = pre[tmpi][tmpj].y;
196                  break;
197              }
198          default: break;
199          }
200      }
201      return(result);
202  }