POJ 3414 Pots【BFS水】

POJ 3414 Pots
大意：有两只桶，容量分别为a,b,对每只桶，有以下三种操作：
1.Fill(i)装满第i只桶
2.DROP(i)将桶i的水倒掉
3.POUR(i,j),将桶i中的水倒入桶j,若桶j满,剩余的水遗留于桶i中

问能否通过这些操作使得某只桶恰好装有容量为c的水？若能，输出最少操作次数及过程
PS:c<max(a,b);

  算法：BFS即可

#include<stdio.h>
#include<string.h>
#include<queue>
usingnamespace std;
constint N =101;
struct pn
{
 int prex;
 int prey;
}pre[N][N];
struct node
{
 int a,b;
 int step;
 booloperator<(const node &A)const
 {
  return A.step<step;
 }
};
bool visited[N][N];
int fa,fb;
void DFS(int a,int b)
{
 if(pre[a][b].prex+pre[a][b].prey!=0)
  DFS(pre[a][b].prex,pre[a][b].prey);
 int pa=pre[a][b].prex;
 int pb=pre[a][b].prey;

 //A清空
if(pa!=0&&a==0&&pb==b)
 {
  printf("DROP(1)\n");
     return;
 }
    
 //装满A
if(pa!=fa&&a==fa&&pb==b)
 {
  printf("FILL(1)\n");
  return;
 }

 //从A倒入B或B倒入A
if(pa+pb==a+b)
 {
  //A->B
if(a==0||b==fb)
  {
           printf("POUR(1,2)\n");
  }
  else
   printf("POUR(2,1)\n");
  return;
 }

 //装满B
if(pa==a&&b==fb)
 {
  printf("FILL(2)\n");
  return;
 }

 printf("DROP(2)\n");
}
void BFS(int a,int b,int c)
{

 fa=a;fb=b;
 priority_queue<node>Q;
 memset(visited,false,sizeof(visited));

 node cur,next;
 cur.a =0;
 cur.b =0;
 cur.step =0;
 Q.push(cur);
 while(!Q.empty())
 {
        cur=Q.top();
        Q.pop();
  if(visited[cur.a][cur.b]==true)continue;
  visited[cur.a][cur.b]=true;
        if(cur.a==c||cur.b==c)break;
  next.step=cur.step+1;
  //将A倒满
  next.a=a;
  next.b=cur.b;
 
  if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }

  //将A清空
  next.a =0;
  next.b = cur.b;
  if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }

  //将A倒入B
  next.a =0;
  next.b = cur.b+cur.a;
  if(next.b>b)
  {
   next.a = next.b-b;
            next.b=b;
  }
  if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }
  //将b清空
  next.a=cur.a;
  next.b =0;
     if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }

  //将b装满
  next.a=cur.a;
  next.b=b;
  if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }

  //将b倒入A
  next.a=cur.a+cur.b;
  next.b=0;
  if(next.a>a)
  {
   next.b=next.a-a;
   next.a=a;
  }
  if(visited[next.a][next.b]==false)
  {
   pre[next.a][next.b].prex=cur.a;
      pre[next.a][next.b].prey=cur.b;
   Q.push(next);
  }

 }

 if(cur.a==c||cur.b==c)
 {
   printf("%d\n",cur.step);

   DFS(cur.a,cur.b);
 }
 else
  printf("impossible\n");
}
int main()
{
 int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF)
 {
  BFS(a,b,c);
 }
 return0;
}