当前位置：首页 > news >正文

Pots bfs（）记录每一种状态，直到求出最优值

news 来源：原创 2024/5/19 18:57:12

Problem Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

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).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6 FILL(2) POUR(2,1) DROP(1) POUR(2,1) FILL(2) POUR(2,1)

***************************************************************************************************************************

bfs（），简单的，记录路径很重要

***************************************************************************************************************************

  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 using namespace std;
  7 int a,b,c;
  8 int vis[1001][1001],step1,lastv;//vis标记数组
  9 int id[10001];
 10 int tail,head,flag;
 11 struct  node
 12 {
 13     int pre;//记录前驱
 14     int k1,k2;//两个桶中的水量
 15     int operation;//操作
 16     int step;//记录步数
 17 }que[10000001],now,next;
 18 void bfs()
 19 {
 20     tail=head=0;
 21         now.k1=0;
 22         now.k2=0;
 23         now.pre=0;
 24         now.operation=0;
 25         now.step=0;
 26         que[tail++]=now;
 27         vis[0][0]=1;
 28         while(head<tail)
 29         {
 30             now=que[head];
 31             head++;
 32             if(now.k1==c||now.k2==c)
 33             {
 34                 flag=1;
 35                 step1=now.step;
 36                 lastv=head-1;
 37                 return;
 38             }
 39             for(int it=0;it<6;it++)//六种操作
 40             {
 41                 if(it==0)//fill(1);
 42                 {
 43                     next.k1=a;
 44                     next.k2=now.k2;
 45                 }
 46                 if(it==1)//fill(2);
 47                  {
 48                      next.k1=now.k1;
 49                      next.k2=b;
 50                  }
 51                 if(it==2)//drop(1);
 52                  {
 53                      next.k1=0;
 54                      next.k2=now.k2;
 55                  }
 56                  if(it==3)//drop(2);
 57                  {
 58                      next.k1=now.k1;
 59                      next.k2=0;
 60                  }
 61                  if(it==4)//pour(1,2);
 62                  {
 63                      if(now.k1+now.k2<=b)
 64                      {
 65                          next.k1=0;
 66                          next.k2=now.k1+now.k2;
 67                      }
 68                      else
 69                      {
 70                          next.k1=now.k1+now.k2-b;
 71                          next.k2=b;
 72                      }
 73                  }
 74                  if(it==5)//pour(2,1);
 75                  {
 76                      if(now.k1+now.k2<=a)
 77                      {
 78                          next.k1=now.k1+now.k2;
 79                          next.k2=0;
 80                      }
 81                      else
 82                      {
 83                          next.k2=now.k1+now.k2-a;
 84                          next.k1=a;
 85                      }
 86                  }
 87                  next.operation=it;
 88                  if(!vis[next.k1][next.k2])//标记检测完退出
 89                  {
 90                      vis[next.k1][next.k2]=1;
 91                      next.step=now.step+1;
 92                      next.pre=head-1;
 93                      //cout<<next.pre<<endl;
 94                      que[tail].k1=next.k1;que[tail].k2=next.k2;
 95                      que[tail].step=next.step;que[tail].pre=next.pre;
 96                      que[tail].operation=next.operation;
 97                      tail++;
 98                  }
 99                  if(next.k1==c||next.k2==c)
100                  {
101                      flag=1;
102                      step1=next.step;
103                      lastv=tail-1;
104                      return;
105 
106                  }
107             }
108 
109         }
110 }
111 int main()
112 {
113     while(scanf("%d%d%d",&a,&b,&c)!=EOF)
114     {
115         flag=0;
116         step1=0;
117         memset(vis,0,sizeof(vis));
118         bfs();
119         if(flag)
120         {
121             printf("%d\n",step1);
122             id[step1]=lastv;
123             for(int i=step1-1;i>=1;i--)
124              {
125                  //printf("que[id[%d+1]].pre: %d\n",que[id[i+1]].pre);
126                  id[i]=que[id[i+1]].pre;
127              }
128             for(int i=1;i<=step1;i++)
129             {
130                 //printf("id[%d]:%d\n",i,id[i]);
131                 if(que[id[i]].operation==0)
132                   printf("FILL(1)\n");
133                 if(que[id[i]].operation==1)
134                   printf("FILL(2)\n");
135                 if(que[id[i]].operation==2)
136                   printf("DROP(1)\n");
137                 if(que[id[i]].operation==3)
138                   printf("DROP(2)\n");
139                 if(que[id[i]].operation==4)
140                   printf("POUR(1,2)\n");
141                 if(que[id[i]].operation==5)
142                   printf("POUR(2,1)\n");
143             }
144         }
145         else
146             printf("impossible\n");
147     }
148     return 0;
149 }