蓝桥杯历届决赛之分红酒
来源：程序员人生 发布时间：2015-08-14 08:52:15 阅读次数：2644次
原题：
有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0]，也就是说：第1个瓶子满着，其它的都空着。
允许把酒从1个瓶子倒入另外一个瓶子，但只能把1个瓶子倒满或把1个瓶子倒空，不能有中间状态。这样的1次
倒酒动作称为1次操作。
假定瓶子的容量和初始状态不变，对给定的目标状态，最少需要多少次操作才能实现？
本题就是要求你编程实现最小操作次数的计算。
输入：终究状态（逗号分隔）
输出：最小操作次数（如没法实现，则输出⑴）
例如：
输入：
9,0,0,0
应当输出：
0
输入：
6,0,0,3
应当输出：
⑴
输入：
7,2,0,0
应当输出：
2
思路：跟我上1篇博客是1样的思路。BFS广度优先搜索。在状态类中由于不需要打印路径，将last值改成存储次数。将瓶子改成4个，容量肯定。不懂的可以先去看我上1篇博客。
java code：
package package1;
import java.util.*;
public class T201207_03 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
//肯定初始状态
int[] s = new int[4];
for(int i = 0;i<s.length;i++)
s[i] = cin.nextInt();
Zt start = new Zt(s,0);
//肯定结束状态
int[] ans = new int[4];
for(int i = 0;i<ans.length;i++)
ans[i] = cin.nextInt();
Zt ansZt = new Zt(ans,⑴);
//创建队列，初始状态入队
Queue<Zt> queue = new LinkedList<Zt>();
queue.add(start);
//声明出队中间变量
Zt temp = null;
Zt newZt = null;
int p = 0;
if(start.equals(ansZt)){
sop("last = "+start.last);
return;
}
while(!queue.isEmpty())
{
//出队
temp = queue.poll();
temp.show();
//倒酒，1->2,1->3,1->4
// 2->1,2->3,2->4
// 3->1,3->2,3->4
//<span style="white-space:pre"> </span>4->1,4->2,4->3
for(int i = 0;i<3;i++)
for(int j = 0;j<3;j++)
{
//相等跳过
if(i == j)
continue;
//产生新的状态
newZt = temp.move(i,j,temp.last+1);
//为空则跳过
if(newZt == null)
continue;
queue.add(newZt);
if(newZt.equals(ansZt))
{
//newZt.show();
sop("last = "+newZt.last);
return;
}
}
}
sop("⑴");
}
private static void sop(String string) {
System.out.println(string);
}
}
//状态类
class Zt
{
//静态容量
public static int[] rl = {9,7,4,2};
//记录次数
int last;
//当前状态
int[] zt = new int[4];
Zt(int[] pz,int p)
{
last = p;
for(int i = 0;i<zt.length;i++)
zt[i] = pz[i];
}
//判断key值是不是存在当前状态
public int indexOf(int key)
{
for(int i = 0;i<zt.length;i++)
{
if(zt[i] == key)
return i;
}
return ⑴;
}
//将i的酒到入j中
public Zt move(int i,int j,int p)
{//比较i瓶的剩余量和j瓶的空闲量
//建立新的状态
int[] newzt = new int[4];
for(int k = 0;k<zt.length;k++)
{
newzt[k] = zt[k];
}
Zt newZt = new Zt(newzt,p);
//没法倒酒返回null
if(newZt.zt[i] == 0||newZt.zt[j] == newZt.rl[j])
return null;
if(newZt.zt[i]<= newZt.rl[j]-newZt.zt[j])
{//i的酒量小于j的剩余量，i清空，j += i
newZt.zt[j] += newZt.zt[i];
newZt.zt[i] = 0;
return newZt;
}
else
{//i的酒量大于j的剩余量，倒满j后i有剩余
newZt.zt[i] -= (newZt.rl[j] - newZt.zt[j]);
newZt.zt[j] = newZt.rl[j];
return newZt;
}
}
public void show()
{
System.out.print("zt = "+this.last+" ");
for(int i = 0;i<zt.length;i++)
System.out.print(zt[i]+",");
sop("");
}
public boolean equals(Object arg0) {
Zt e = (Zt)arg0;
for(int i = 0;i<zt.length;i++){
if(zt[i]!=e.zt[i])
return false;
}
return true;
}
private static void sop(String string) {
System.out.println(string);
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
