nyoj 题目21 三个水杯

三个水杯

时间限制：1000 ms | 内存限制：65535 KB

难度：4

描述: 给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

样例输出

3

-1

虽然一看就知道用广度优先搜索，但是具体怎么做却还需要动一番脑筋。
代码如下

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 using namespace std;

 struct Bottle {

     int v[];

     int step;

     Bottle() {};

     Bottle(int u, int v, int w, int s) {

         this->v[] = u; this->v[] = v; this->v[] = w;

         step = s;

     }

 };

 queue <Bottle> bot;

 int visit[][][];

 bool isEqual(Bottle p, int e[]) {

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

         if(p.v[i] != e[i]) {

             return false;

         }

     }

     return true;

 }

 int main(int argc, char const *argv[])

 {

     int N;

     scanf("%d",&N);

     while(N--) {

         int v[];

         int e[];

         scanf("%d %d %d",&v[],&v[],&v[]);

         scanf("%d %d %d",&e[],&e[],&e[]);

         while(!bot.empty()) {

             bot.pop();

         }

         memset(visit, , sizeof(visit));

         bot.push(Bottle(v[],,,));

         int ans = -;

         while(!bot.empty()) {

             Bottle p = bot.front();

             bot.pop();

             if(isEqual(p,e))

             {

                 ans = p.step;

                 break;

             }

             else {

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

                     for(int j = ; j < ; j++) {

                         int k = (i+j)%;

                         //from i to k

                         if(p.v[i] >  && p.v[k] < v[k]) {

                             int cha = v[k] - p.v[k];

                             int pour = min(p.v[i], cha);

                             Bottle t;

                             t.v[i] = p.v[i] - pour;

                             t.v[k] = p.v[k] + pour;

                             t.v[-i-k] = p.v[-i-k];

                             t.step = p.step+;

                             if(visit[t.v[]][t.v[]][t.v[]] != ) {

                                 visit[t.v[]][t.v[]][t.v[]] = ;

                                 bot.push(t);

                             }

                         }

                     }

                 }

             }

         }

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

     }

     return ;

 }

巴特西

nyoj 题目21 三个水杯

三个水杯

最新文章

热门文章