Pots(bfs)

题意：给出1号杯子的容量a，2号杯子的容量b，目标盛水量c。问两个杯子经过怎样的变换能盛出c容量的水，输出最小步数及转换过程，如不能转换，输出“‘impossible”。

思路：总共有6种转换，bfs搜索每一种转换，并记录前一个状态。最后将记录的状态倒着输出。

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string.h>
  4 #include <queue>
  5 #include <stack>
  6 const int N=112;
  7 using namespace std;
  8 string oper[7] = {"","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(2,1)","POUR(1,2)"}; 
  9                  //六种操作
 10 int a,b,c,vis[N][N],keep[N];//vis[][]用来标记当前状态，keep[][]用来存储记录的id   
 11 struct node
 12 {
 13     int x;
 14     int y;
 15     int step;
 16 };
 17 struct path
 18 {
 19     int x;
 20     int y;
 21     int id;
 22 } pre[N][N];//记录当前状态下的前一个状态
 23 void show(int x,int y)
 24 {
 25     int k = 0;
 26     while (x||y)
 27     {
 28         int xx = pre[x][y].x;
 29         int yy = pre[x][y].y;
 30         int id = pre[x][y].id;
 31         x = xx;
 32         y = yy;
 33         keep[k++] = id;//存储达到目标存水量c的之前的操作id
 34     }
 35     for (int i = k-1; i >= 0; i --)
 36         cout<<oper[keep[i]]<<endl;
 37 
 38 }
 39 void bfs()
 40 {
 41     queue<node>q;
 42     q.push((struct node)
 43     {
 44         0,0,0
 45     });
 46     vis[0][0] = 1;
 47     while(!q.empty())
 48     {
 49         node t = q.front();
 50         q.pop();
 51         if (t.x==c||t.y==c)
 52         {
 53             printf("%d
",t.step);
 54             show(t.x,t.y);
 55             return ;
 56         }
 57         if(t.x < a && !vis[a][t.y])//FILL(1)
 58         {
 59             q.push((struct node){a,t.y,t.step+1});
 60             vis[a][t.y] = 1;
 61             pre[a][t.y] = (struct path){t.x,t.y,1};
 62         }
 63         if (t.y < b && !vis[t.x][b])//FILL(2)
 64         {
 65             q.push((struct node){t.x,b,t.step+1});
 66             vis[t.x][b] = 1;
 67             pre[t.x][b] = (struct path){t.x,t.y,2};
 68         }
 69         if (t.x > 0 && !vis[0][t.y])//DROP(1)
 70         {
 71             q.push((struct node){0,t.y,t.step+1});
 72             vis[0][t.y] = 1;
 73             pre[0][t.y] = (struct path){t.x,t.y,3};
 74         }
 75         if (t.y > 0 && !vis[t.x][0])//DROP(2)
 76         {
 77             q.push((struct node){t.x,0,t.step+1});
 78             vis[t.x][0] = 1;
 79             pre[t.x][0] = (struct path){t.x,t.y,4};
 80         }
 81         if (t.y > 0 && t.x < a)//POUR(2,1)
 82         {
 83             int m = min(a-t.x,t.y);
 84             if (!vis[t.x+m][t.y-m])
 85             {
 86                 q.push((struct node){t.x+m,t.y-m,t.step+1});
 87                 vis[t.x+m][t.y-m] = 1;
 88                 pre[t.x+m][t.y-m] = (struct path){t.x,t.y,5};
 89             }
 90         }
 91         if (t.x > 0 && t.y < b)//POUR(1,2)
 92         {
 93             int m = min(b-t.y,t.x);
 94             if (!vis[t.x-m][t.y+m])
 95             {
 96                 q.push((struct node){t.x-m,t.y+m,t.step+1});
 97                 vis[t.x-m][t.y+m] = 1;
 98                 pre[t.x-m][t.y+m] = (struct path){t.x,t.y,6};
 99             }
100         }
101     }
102     printf("impossible
");
103 }
104 int main()
105 {
106     scanf("%d%d%d",&a,&b,&c);
107     memset(vis,0,sizeof(vis));
108     bfs();
109     return 0;
110 }

View Code