poj 3414 Pots bfs+模拟

#include<iostream>
#include<cstring>
#define fillA 1
#define pourAB 2
#define dropA 3
#define fillB 4
#define pourBA 5
#define dropB 6

#define N 10000

using namespace std;
int vis[105][105];
class node
{
public:
   int A, B;
   int dir;
   node()
   {
      A=0;
      B=0;
   }
};

int a, b, c, tot;
node q[N];
int pre[N];

void printPath(int index)
{
   if(index==0)
   {
       cout<<tot<<endl;
       return ;
   }
   ++tot;
   printPath(pre[index]);
   switch(q[index].dir)
   {
      case 1:
           cout<<"FILL(1)";
           break;
      case 2:
           cout<<"POUR(1,2)";
           break;
      case 3:
           cout<<"DROP(1)";
           break;
      case 4:
           cout<<"FILL(2)";
           break;
      case 5:
           cout<<"POUR(2,1)";
           break;
      case 6:
           cout<<"DROP(2)";
           break;
   }
   cout<<endl;
}

int bfs()
{
   int head=0, rear=1, r;
   node cur, next;
   memset(vis, 0, sizeof(vis));
   pre[0]=0;
   vis[0][0]=1;
   while(head<rear)
   {
       cur=q[head];
       if(cur.A==c || cur.B==c)
       {
             printPath(head);
             return 1;
       }
       next=cur;
       if(!vis[a][cur.B])//将 A 装满
       {
             next.A=a;
             next.dir=fillA;
             pre[rear]=head;
             vis[a][cur.B]=1;
             q[rear++]=next;
       }
       if(!vis[0][cur.B])//将 A 倒掉
       {
             next.A=0;
             next.dir=dropA;
             pre[rear]=head;
             vis[0][cur.B]=1;
             q[rear++]=next;
       }
       r=b-cur.B;
       next.dir=pourAB;
       if(r>cur.A && !vis[0][cur.B+cur.A])//将A 倒向 B
       {
             next.A=0;
             next.B=cur.B+cur.A;
             pre[rear]=head;
             q[rear++]=next;
             vis[0][cur.B+cur.A]=1;
       }
       else if(r<=cur.A && !vis[cur.A-r][cur.B+r])
       {
             next.A=cur.A-r;
             next.B=cur.B+r;
             pre[rear]=head;
             q[rear++]=next;
             vis[cur.A-r][cur.B+r]=1;
       }

       next=cur;//开始错在这里了， 忘记了从新给next赋值了
       if(!vis[cur.A][b])//将 B 装满
       {
             next.B=b;
             next.dir=fillB;
             pre[rear]=head;
             q[rear++]=next;
             vis[cur.A][b]=1;
       }
       if(!vis[cur.A][0])//将 B 倒掉
       {
             next.B=0;
             next.dir=dropB;
             pre[rear]=head;
             q[rear++]=next;
             vis[cur.A][0]=1;
       }
       r=a-cur.A;
       next.dir=pourBA;
       if(r>cur.B && !vis[cur.B+cur.A][0])//将B 倒向 A
       {
             next.B=0;
             next.A=cur.B+cur.A;
             pre[rear]=head;
             q[rear++]=next;
             vis[cur.B+cur.A][0]=1;
       }
       else if(r<=cur.B && !vis[cur.A+r][cur.B-r])
       {
             next.A=cur.A+r;
             next.B=cur.B-r;
             pre[rear]=head;
             q[rear++]=next;
             vis[cur.A+r][cur.B-r]=1;
       }
      ++head;
   }
   return 0;
}

int main()
{
   while(cin>>a>>b>>c)
   {
      tot=0;
      if(c>a && c>b)
      {
         cout<<"impossible"<<endl;
         continue;
      }
      if(!bfs())
         cout<<"impossible"<<endl;
   }
   return 0;
}