Pots

poj3414:http://poj.org/problem?id=3414

题意：给你两个罐子的体积，然后让你只用这两个罐子量出给定k体积的水。
题解：这里可以把两个罐子看成是一个二维的图，然后体积的水就是图中其中一个坐标是k的点。可以直接BFS，每次操作就相当于从当前的点向外扩展，并且记录当前的路径，即可。
其中可以用1,2,3,4,5,6六个数字来分别对应六种操作，然后用一个int类型的数组记录路径就可以。

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cstdio>

#include<queue>

using namespace std;

struct Node{

  int counts1;//第一个pot中当前的水

  int counts2;//第二个pot中当前的水

  int step;//当前的步数

  int path[];//记录到达这一步之前的以及这一步的路径

};

int counts[][];//counts【i】【j】表示到达第一个pot中是i，

int a,b,k;          //第二个pot中是j这种状态所需要的最小的步数

void print(int x){//打印出对印标记的输出路径上每一个数字代表一种操作，六个数字对印六种操作

  if(x==)printf("FILL(1)\n");

  if(x==)printf("FILL(2)\n");

  if(x==)printf("DROP(1)\n");

  if(x==)printf("DROP(2)\n");

  if(x==)printf("POUR(2,1)\n");

  if(x==)printf("POUR(1,2)\n");

}

void  BFS(){

    bool flag=false;//标记是否有解

   for(int i=;i<=;i++)

    for(int j=;j<=;j++)//初始化

      counts[i][j]=;

     queue<Node>Q;

     Node tt;//队首元素

     tt.counts1=;//初始时候都是0,0

     tt.counts2=;

     tt.step=;

     counts[][]=;//别忘了注意这里的初始化0

     Q.push(tt);

     while(!Q.empty()){

        Node temp=Q.front();//取出队首元素

        Q.pop();

        int  step=temp.step;

        int  sum1=temp.counts1;

        int  sum2=temp.counts2;

        if(sum1==k){//只要其中一个罐子出现k，则直接输出

                printf("%d\n",step);

               for(int i=;i<=step;i++)//输出路径

                 print(temp.path[i]);

                 flag=true;

                  break;

             }

        if(sum2==k){

              printf("%d\n",step);

               for(int i=;i<=step;i++)

                print(temp.path[i]);

                flag=true;

                 break;

            }

        if(sum1<a&&counts[a][sum2]>step+){//当第一个罐子没满，这是可以把第一个罐子灌满

            Node ttt;

            ttt.counts1=a;

            ttt.counts2=sum2;

            ttt.step=step+;

            for(int i=;i<=step;i++)//复制之前的路径

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[a][sum2]=step+;

        }

         if(sum2<b&&counts[sum1][b]>step+){//灌满第二个罐子

            Node ttt;

            ttt.counts1=sum1;

            ttt.counts2=b;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[sum1][b]=step+;

        }

      if(sum1>&&counts[][sum2]>step+){//清空第一个罐子

            Node ttt;

            ttt.counts1=;

            ttt.counts2=sum2;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[][sum2]=step+;

        }

         if(sum2>&&counts[sum1][]>step+){//清空第二个罐子

            Node ttt;

            ttt.counts1=sum1;

            ttt.counts2=;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[sum1][]=step+;

        }

          if(sum2+sum1>=a&&counts[a][sum2+sum1-a]>step+){//把第二个导入第一个并且第一个装满之后，第二个还有剩余

            Node ttt;

            ttt.counts1=a;

            ttt.counts2=sum2+sum1-a;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[a][sum2+sum1-a]=step+;

        }

         if(sum2+sum1<a&&counts[sum1+sum2][]>step+){////把第二个导入第一个并且第一个装满之后，第二个没有剩余

            Node ttt;

            ttt.counts1=sum1+sum2;

            ttt.counts2=;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[sum1+sum2][]=step+;

        }

         if(sum2+sum1>=b&&counts[sum1+sum2-b][b]>step+){//与上面正好相反

            Node ttt;

            ttt.counts1=sum1+sum2-b;

            ttt.counts2=b;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[sum1+sum2-b][b]=step+;

        }

         if(sum2+sum1<b&&counts[][sum1+sum2]>step+){

            Node ttt;

            ttt.counts1=;

            ttt.counts2=sum1+sum2;

            ttt.step=step+;

             for(int i=;i<=step;i++)

                ttt.path[i]=temp.path[i];

            ttt.path[step+]=;

            Q.push(ttt);

            counts[][sum1+sum2]=step+;

        }

     }

     if(!flag)printf("impossible\n");

}

int main(){

    scanf("%d%d%d",&a,&b,&k);

    BFS();

}