poj 3414 Pots （ bfs ）

题意：给出了两个瓶子的容量A,B, 以及一个目标水量C，

对A、B可以有如下操作:

FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;

DROP(i) empty the pot i to the drain;

POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

问经过哪几个操作后能使得任意一个瓶子的残余水量为C。

若不可能得到则输出impossible

  1 #include <iostream>
  2  #include<cstdio>
  3  #include<cstring>
  4  #include<cstdlib>
  5  #include<stack>
  6  #include<queue>
  7  #include<iomanip>
  8  #include<cmath>
  9  #include<map>
 10  #include<vector>
 11  #include<algorithm>
 12  using namespace std;
 13  
 14  int vis[110][110];
 15  int a,b,c;
 16  struct node
 17  {
 18      int x,y,step;
 19  }pos,next;
 20  
 21  struct way
 22  {
 23      int x,y,f;
 24  }before[110][110];
 25  
 26  void pri(int x,int y)
 27  {
 28      stack<int>st;
 29      while(x!=0||y!=0)
 30      {
 31          st.push(before[x][y].f);
 32          int  tx=before[x][y].x;
 33          int ty=before[x][y].y;
 34          x=tx; y=ty;
 35      }
 36      while(!st.empty())
 37      {
 38          switch(st.top())
 39          {
 40              case 1:printf("DROP(1)
"); break;
 41              case 2:printf("DROP(2)
"); break;
 42              case 3:printf("FILL(1)
"); break;
 43              case 4:printf("FILL(2)
"); break;
 44              case 5:printf("POUR(1,2)
"); break;
 45              case 6:printf("POUR(2,1)
"); break;
 46          }
 47          st.pop();
 48      }
 49  }
 50  int bfs()
 51  {
 52      queue<node>q;
 53      next.x=0; next.y=0; next.step=0;
 54      vis[0][0]=1;
 55      q.push(next);
 56      while(!q.empty())
 57      {
 58          pos=q.front();
 59          //cout<<pos.x<<" "<<pos.y<<" "<<pos.step<<"    ";
 60          //cout<<before[pos.x][pos.y].x<<" "<<before[pos.x][pos.y].y<<" "<<before[pos.x][pos.y].f<<endl;
 61          q.pop();
 62          if(pos.x==c||pos.y==c)
 63          {
 64              cout<<pos.step<<endl;
 65              pri(pos.x,pos.y);
 66              return 1;
 67          }
 68          if(!vis[0][pos.y]&&pos.x!=0)
 69          {
 70              next.x=0; next.y=pos.y; next.step=pos.step+1;
 71              q.push(next);
 72              vis[0][pos.y]=1;
 73              before[0][pos.y]=(struct way){pos.x,pos.y,1};
 74          }
 75          if(!vis[pos.x][0]&&pos.y!=0)
 76          {
 77              next.x=pos.x; next.y=0; next.step=pos.step+1;
 78              q.push(next);
 79              vis[pos.x][0]=1;
 80              before[pos.x][0]=(struct way){pos.x,pos.y,2};
 81          }
 82          if(!vis[a][pos.y]&&pos.x!=a)
 83          {
 84              next.x=a; next.y=pos.y; next.step=pos.step+1;
 85              q.push(next);
 86              vis[a][pos.y]=1;
 87              before[a][pos.y]=(struct way){pos.x,pos.y,3};
 88          }
 89          if(!vis[pos.x][b]&&pos.y!=b)
 90          {
 91              next.x=pos.x; next.y=b; next.step=pos.step+1;
 92              q.push(next);
 93              vis[pos.x][b]=1;
 94              before[pos.x][b]=(struct way){pos.x,pos.y,4};
 95          }
 96          if(pos.x>0&&pos.y<b)
 97          {
 98              int t=min(pos.x,b-pos.y);
 99              if(!vis[pos.x-t][pos.y+t])
100              {
101                  q.push((struct node){pos.x-t,pos.y+t,pos.step+1});
102                  vis[pos.x-t][pos.y+t]=1;
103                  before[pos.x-t][pos.y+t]=(struct way){pos.x,pos.y,5};
104              }
105          }
106          if(pos.x<a&&pos.y>0)
107          {
108              int t=min(pos.y,a-pos.x);
109              if(!vis[pos.x+t][pos.y-t])
110              {
111                  q.push((struct node){pos.x+t,pos.y-t,pos.step+1});
112                  vis[pos.x+t][pos.y-t]=1;
113                  before[pos.x+t][pos.y-t]=(struct way){pos.x,pos.y,6};
114              }
115          }
116      }
117      return 0;
118  }
119  int main()
120  {
121      cin>>a>>b>>c;
122      memset(vis,0,sizeof(vis));
123      if(bfs()==0)
124      cout<<"impossible"<<endl;
125      return 0;
126  }
127