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
原题出自：http://acm.nyist.net/JudgeOnline/problem.php?pid=21

简单的宽度优先搜索，三个水杯之间的相互倒水如下图6种情况：

对于每一次倒水都会引起三个水杯水量状态的改变，这样就可以得到如下的一个解空间树：

代码一：比较容易想到的

  1 #include<cstring>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cstdlib>
  6 using namespace std;
  7 
  8 int v1, v2, v3;
  9 bool visit[105][105][105]; //状态是否出现
 10 
 11 struct state
 12 {
 13     int a, b, c;
 14     int ceng; //最小步数
 15 }b, e;
 16 
 17 int BFS()
 18 {
 19     queue<state> q;
 20     while(!q.empty())
 21         q.pop();
 22     q.push(b);
 23     while(!q.empty())
 24     {
 25         state cur = q.front(); 
 26         q.pop();
 27         visit[cur.a][cur.b][cur.c] = true;
 28 
 29         if(cur.a == e.a && cur.b == e.b && cur.c == e.c) //找到
 30             return cur.ceng;
 31 
 32         if(cur.a > 0 && cur.b < v2)                    //v1->v2
 33         {
 34             state temp = cur;
 35             int tt = min(temp.a, v2 - temp.b);
 36             temp.a -= tt;
 37             temp.b += tt;
 38             if(visit[temp.a][temp.b][temp.c] == false)
 39             {
 40                 visit[temp.a][temp.b][temp.c] = true;
 41                 temp.ceng++;
 42                 q.push(temp);
 43             }
 44         }
 45 
 46         if(cur.a > 0 && cur.c < v3)                    //v1->v3
 47         {
 48             state temp = cur;
 49             int tt = min(temp.a, v3 - temp.c);
 50             temp.a -= tt;
 51             temp.c += tt;
 52             if(visit[temp.a][temp.b][temp.c] == false)
 53             {
 54                 visit[temp.a][temp.b][temp.c] = true;
 55                 temp.ceng++;
 56                 q.push(temp);
 57             }
 58         }
 59 
 60         if(cur.b > 0 && cur.a < v1)                    //v2->v1
 61         {
 62             state temp = cur;
 63             int tt = min(temp.b, v1 - temp.a);
 64             temp.a += tt;
 65             temp.b -= tt;
 66             if(visit[temp.a][temp.b][temp.c] == false)
 67             {
 68                 visit[temp.a][temp.b][temp.c] = true;
 69                 temp.ceng++;
 70                 q.push(temp);
 71             }
 72         }
 73 
 74         if(cur.b > 0 && cur.c < v3)                    //v2->v3
 75         {
 76             state temp = cur;
 77             int tt = min(temp.b, v3 - temp.c);
 78             temp.b -= tt;
 79             temp.c += tt;
 80             if(visit[temp.a][temp.b][temp.c] == false)
 81             {
 82                 visit[temp.a][temp.b][temp.c] = true;
 83                 temp.ceng++;
 84                 q.push(temp);
 85             }
 86         }
 87 
 88         if(cur.c > 0 && cur.a < v1)                    //v3->v1
 89         {
 90             state temp = cur;
 91             int tt = min(temp.c, v1 - temp.a);
 92             temp.c -= tt;
 93             temp.a += tt;
 94             if(visit[temp.a][temp.b][temp.c] == false)
 95             {
 96                 visit[temp.a][temp.b][temp.c] = true;
 97                 temp.ceng++;
 98                 q.push(temp);
 99             }
100         }
101 
102         if(cur.c > 0 && cur.b < v2)                    //v3->v2
103         {
104             state temp = cur;
105             int tt = min(temp.c, v2 - temp.b);
106             temp.c -= tt;
107             temp.b += tt;
108             if(visit[temp.a][temp.b][temp.c] == false)
109             {
110                 visit[temp.a][temp.b][temp.c] = true;
111                 temp.ceng++;
112                 q.push(temp);
113             }
114         }
115     }
116     return -1; //没有终状态
117 }
118 
119 int main()
120 {
121     int n;
122     scanf("%d", &n);
123     while(n--)
124     {
125         memset(visit, false, sizeof(visit));
126         scanf("%d %d %d", &v1, &v2, &v3);
127         b.a = v1, b.b = 0, b.c = 0, b.ceng = 0;
128         scanf("%d %d %d", &e.a, &e.b, &e.c);
129         if(v1 < e.a + e.b + e.c)
130         {
131             printf("-1
");
132             continue;
133         }
134         else
135             printf("%d
", BFS());
136     }
137     return 0;
138 }

方法二：Floyd 算法

Floyd 算法介绍：http://www.cnblogs.com/orange1438/p/4054649.html

  1 #include <cstdio>
  2 #include <memory.h>
  3 #include <queue>
  4 
  5 using namespace std;
  6 
  7 #define EMPTY    0
  8 
  9 struct data_type
 10 {
 11     int state[3];
 12     int step;
 13 };
 14 
 15 int cupCapacity[3], targetState[3];
 16 
 17 bool visited[100][100][100];
 18 
 19 bool AchieveTargetState(data_type current)
 20 {
 21     for (int i = 0; i < 3; i++)
 22     {
 23         if (current.state[i] != targetState[i])
 24         {
 25             return false;
 26         }
 27     }
 28     return true;
 29 }
 30 
 31 void PourWater(int destination, int source, data_type &cup)
 32 {
 33     int waterYield = cupCapacity[destination] - cup.state[destination];
 34     if (cup.state[source] >= waterYield)
 35     {
 36         cup.state[destination] += waterYield;
 37         cup.state[source] -= waterYield;
 38     }
 39     else
 40     {
 41         cup.state[destination] += cup.state[source];
 42         cup.state[source] = 0;
 43     }
 44 }
 45 
 46 int BFS(void)
 47 {
 48     int i, j, k;
 49     data_type initial;
 50     queue<data_type> toExpandState;
 51 
 52     memset(visited, false, sizeof(visited));
 53     initial.state[0] = cupCapacity[0];
 54     initial.state[1] = initial.state[2] = 0;
 55     initial.step = 0;
 56     toExpandState.push(initial);
 57     visited[initial.state[0]][0][0] = true;
 58 
 59     while (!toExpandState.empty())
 60     {
 61         data_type node = toExpandState.front();
 62         toExpandState.pop();
 63         if (AchieveTargetState(node))
 64         {
 65             return node.step;
 66         }
 67         for (i = 0; i < 3; i++)
 68         {
 69             for (j = 1; j < 3; j++)
 70             {
 71                 k = (i+j)%3;
 72                 if (node.state[i] != EMPTY && node.state[k] < cupCapacity[k])
 73                 {
 74                     data_type newNode = node;
 75                     PourWater(k, i, newNode);
 76                     newNode.step = node.step + 1;
 77                     if (!visited[newNode.state[0]][newNode.state[1]][newNode.state[2]])
 78                     {
 79                         visited[newNode.state[0]][newNode.state[1]][newNode.state[2]] = true;
 80                         toExpandState.push(newNode);
 81                     }
 82                 }
 83             }
 84         }
 85     }
 86     return -1;
 87 }
 88 
 89 int main(void)
 90 {
 91     int testNum;
 92     scanf("%d", &testNum);
 93     while (testNum -- != 0)
 94     {
 95         scanf("%d%d%d", &cupCapacity[0], &cupCapacity[1], &cupCapacity[2]);
 96         scanf("%d%d%d", &targetState[0], &targetState[1], &targetState[2]);
 97         printf("%d
", BFS());
 98     }
 99     return 0;
100 }

部分转自：http://blog.csdn.net/code_pang/article/details/7802944