POJ 3414 Pots

这个题目可有意思了，小时候我爸爸也经常会出这样的考我。题意：给你两个容量为a,b的容器，分别有几种操作，分别是：将a倒掉，将b倒掉，将a加满，将b加满，将a倒入b,将b倒入a,六种操作，只要有一个达到c就完成了，求最少的步数，并输出过程。就是一个模拟的过程，然后用广搜需找最少步数，我写的好懂但有点长。

代码：

[cpp]
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
struct Element
{
       int x,y,r;
       Element(int n,int m,int s):x(n),y(m),r(s){}
       Element(){}
};
bool visit[105][105]; //记录状态，如果某个状态前面已经有了不必在扩展，不然步数不可能最小。
Element que[1000005];
int pre[1000005]; //用它记录某个操作的前面的操作是什么
int a,b,c;
void Fn(int&first,int&rear,int x,int y,int r)
{
     if( !visit[x][y]){
         que[rear]=Element(x,y,r);
         pre[rear++]=first;
         visit[x][y]=true;
     }
}

int BFS()
{
    int first,rear;
    Element front;
    first=rear=0;
    memset(que,0,sizeof(que));
    memset(pre,-1,sizeof(pre));
    memset(visit,false,sizeof(visit));

    visit[0][0]=true;
    que[rear++]=Element(0,0,0);
    while( first!=rear){
           front=que[first];
          // printf("%d %d\n",front.x,front.y);
           if( front.x==c||front.y==c)
               return first;

           if( front.x!=a) //将a倒满行为编号1
               Fn(first,rear,a,front.y,1);


           if( front.y!=b) //将b倒满行为编号2
             Fn(first,rear,front.x,b,2);

           if( front.x!=0) //将a倒掉行为编号3
               Fn(first,rear,0,front.y,3);


           if( front.y!=0) //将b倒掉行为编号4
                Fn(first,rear,front.x,0,4);

           if( front.x!=0&&front.y!=b){ //将a倒b 行为编号5

               if( front.x<=b-front.y)
                   Fn(first,rear,0,front.x+front.y,5);
               else
                    Fn(first,rear,front.x+front.y-b,b,5);
           }

           if( front.y!=0&&front.x!=a){ //将b倒a 行为编号6
               if( front.y<=a-front.x)
                   Fn(first,rear,front.x+front.y,0,6);
               else
                    Fn(first,rear,a,front.x+front.y-a,6);
           }
           first++;
           //system("pause");
    }
    return -1;
}

void Solve(int j)
{
     int ans[1000],i,k;
     for( i=j,k=0; pre[i]!=-1; i=pre[i]){
          ans[k++]=que[i].r;
     }
     printf("%d\n",k);
     for( i=k-1; i>=0; i--){
          switch( ans[i]){
                  case 1: printf("FILL(1)\n"); break;
                  case 2: printf("FILL(2)\n"); break;
                  case 3: printf("DROP(1)\n"); break;
                  case 4: printf("DROP(2)\n"); break;
                  case 5: printf("POUR(1,2)\n"); break;
                  case 6: printf("POUR(2,1)\n"); break;
                  default: ;
          }
     } www.zzzyk.com
}
int main()
{
    int f;
    while( scanf("%d%d%d",&a,&b,&c)!=EOF){
           f=BFS();
  &nb

补充：软件开发 , C++ ,