ACM练习实战(一)

好久没做ACM的题库了,今天比工作之余挑了几道题做做。

俗话说得好:每天AC一道题,一年365道题,你就能成为一个编程高手 


一开始做了些简单题,一次性通过:

2521836 huayuwenhao 奇偶数分离 Accepted 0 2312 C/C++ 07-06 13:41:55

后来找了难度系数比较高的尝试了一下
其中一道题目,题目如下:

三个水杯

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


输入
第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行,第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 (体积小于等于相应水杯体积)表示我们需要的最终状态
输出
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
样例输入
2
6 3 1
4 1 1
9 3 2
7 1 1
样例输出
3
-1

不得不说刚开始做这道题的时候,题目没有理解清楚,有一句话非常重要“水杯没有标识,只能根据给出的水杯体积来计算”这句话意味着说,不能够直接123的来标识水杯,其次倒水也不是±1的倒法,是能倒多少倒多少,每倒一次都是让被倒得被子完全放满的,于是这样一看一道本以为非常简单的题,变成了一下次非常没有头绪的题。

思考了一番,既然不是普通方法那必然就是就用数据结构和算法咯

根据题目,可以知道求的是最少次数,那就和最短路径的想法类似。

类比的,最短路径就是从一个点到另一个点各种走法中最早抵达的查找,那这个道题便是从一个状态到另一个状态的各种倒水方法中次数最少的查找。

由于是三个杯子,每个杯子可以给另外两个杯子倒水,也就是说每次枚举所有倒水的可能方法一共有六种。

根据无向图中查找最短路径,一般都采用BFS(广度优先搜索),那么BFS的实质又是链表。于是便建立了以下node

typedef struct Node
{
int x,y,z;
int step;
Node* next;
};

未完持续………………….

发表评论

电子邮件地址不会被公开。 必填项已用*标注