题目
三个水杯
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
输入
第一行一个整数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
思路
其实第一次遇到这个题,我一点思路都没有,现在这个解法也是看了别人的C代码,理解后决定记录一下,顺北实现一下Java版本的.
其实说是BFS,也就是暴力破解,这道题也有很多变种,但这个应该是可以应对其他变种的一种解法.
首先我们需要将三杯水的状态和操作的步骤数封装成类,(其实不用类也可以,就是不方便)然后创建一个队列,将初始状态放进队列,然后进入循环,每次取出对头的状态,先和最终状态比较,看是否满足,满足就退出,否则进行变换,如果这个状态没有出现过就放进队列中,直到队列为空,如果还是,没有满足的状态,就返回-1;
这里的重点就是这个变换,其实就是两杯水x,y,x->y.如果x中有水且y不满,就把x中的水倒入y中,这里有两种情况,一种是将y倒满,另一种是x为空,当然可能二者同时发生,但必须发生一个.
代码
public class Solution {
/**
* 状态内部类,实现深拷贝,很重要
*/
static class State implements Cloneable {
int[] s ;
int step ;
public State(int x,int y ,int z){
s = new int[]{x,y,z};
step = 0 ;
}
@Override
public Object clone() {
try {
State ss = (State)super.clone();
// 深拷贝数组,坑
ss.s = this.s.clone();
return ss ;
} catch (CloneNotSupportedException e) {
return null;
}
}
}
//最终状态,减少方法参数
static int[] endState ;
/**
* 查找改状态变成最终状态的步数,如果不行,返回-1
* @param s 初始状态
* @return step or -1
*/
private static int BFS(State s) {
// 初始状态
State initial = new State(s.s[0],0,0);
// 存储状态的队列
LinkedList ls = new LinkedList<>();
// 判断某一状态是否出现过
int[][][] isVisited = new int[s.s[0]+1][s.s[1]+1][s.s[2]+1];
isVisited[initial.s[0]][0][0] = 1;
ls.addLast(initial);
//进入循环
while (!ls.isEmpty()){
// 取出头元素
State temp = ls.pop();
// 判断是否和最终状态相同
if (isArchive(temp)){
return temp.step;
}
// 对每一个状态进行变换
for (int i = 0 ; i < 3 ; i++){
for (int j = 0 ; j < 3 ;j++){
if (i != j && temp.s[i] != 0 && temp.s[j] < s.s[j]){
State cur = (State) temp.clone();
// i -> j 倒水
pourWater(i,j,cur,s);
// 步数+1
cur.step+=1;
// 如果没有被访问,就添加进入队列
if (isVisited[cur.s[0]][cur.s[1]][cur.s[2]] == 0){
isVisited[cur.s[0]][cur.s[1]][cur.s[2]] =1 ;
ls.addLast(cur);
}
}
}
}
}
return -1 ;
}
/**
* i -> j倒水
* @param i 源杯
* @param j 目的杯
* @param cur 当前状态
* @param capacity 杯子容量
*/
private static void pourWater(int i, int j, State cur,State capacity) {
int waterNeeded = capacity.s[j] - cur.s[j];
if (waterNeeded <= cur.s[i]){
cur.s[j] += waterNeeded; //start.s[j]
cur.s[i] -= waterNeeded;
}else{
cur.s[j] += cur.s[i];
cur.s[i] = 0 ;
}
}
/**
* 判断当前状态是否满足最终状态
* @param cur 当前状态
*/
private static boolean isArchive(State cur) {
if (cur == null){
return false;
}
for (int i = 0 ; i < 3 ;i++){
if (cur.s[i] != endState[i]){
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for (int i = 0 ; i < n ;i++){
int x = scan.nextInt(),y = scan.nextInt(),z = scan.nextInt();
State s = new State(x,y,z);
endState = new int[]{scan.nextInt(),scan.nextInt(),scan.nextInt()};
int step = BFS(s);
System.out.println(step);
}
}
}
代码中的注释很详细,很容易看懂.
