藍(lán)橋杯歷屆決賽之分紅酒
來源：程序員人生 發(fā)布時(shí)間：2015-08-14 08:52:15 閱讀次數(shù)：2791次
原題：
有4個(gè)紅酒瓶子，它們的容量分別是：9升, 7升, 4升, 2升
開始的狀態(tài)是 [9,0,0,0]，也就是說：第1個(gè)瓶子滿著，其它的都空著。
允許把酒從1個(gè)瓶子倒入另外一個(gè)瓶子，但只能把1個(gè)瓶子倒?jié)M或把1個(gè)瓶子倒空，不能有中間狀態(tài)。這樣的1次
倒酒動作稱為1次操作。
假定瓶子的容量和初始狀態(tài)不變，對給定的目標(biāo)狀態(tài)，最少需要多少次操作才能實(shí)現(xiàn)？
本題就是要求你編程實(shí)現(xiàn)最小操作次數(shù)的計(jì)算。
輸入：終究狀態(tài)（逗號分隔）
輸出：最小操作次數(shù)（如沒法實(shí)現(xiàn)，則輸出⑴）
例如：
輸入：
9,0,0,0
應(yīng)當(dāng)輸出：
0
輸入：
6,0,0,3
應(yīng)當(dāng)輸出：
⑴
輸入：
7,2,0,0
應(yīng)當(dāng)輸出：
2
思路：跟我上1篇博客是1樣的思路。BFS廣度優(yōu)先搜索。在狀態(tài)類中由于不需要打印路徑，將last值改成存儲次數(shù)。將瓶子改成4個(gè)，容量肯定。不懂的可以先去看我上1篇博客。
java code：
package package1;
import java.util.*;
public class T201207_03 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
//肯定初始狀態(tài)
int[] s = new int[4];
for(int i = 0;i<s.length;i++)
s[i] = cin.nextInt();
Zt start = new Zt(s,0);
//肯定結(jié)束狀態(tài)
int[] ans = new int[4];
for(int i = 0;i<ans.length;i++)
ans[i] = cin.nextInt();
Zt ansZt = new Zt(ans,⑴);
//創(chuàng)建隊(duì)列，初始狀態(tài)入隊(duì)
Queue<Zt> queue = new LinkedList<Zt>();
queue.add(start);
//聲明出隊(duì)中間變量
Zt temp = null;
Zt newZt = null;
int p = 0;
if(start.equals(ansZt)){
sop("last = "+start.last);
return;
}
while(!queue.isEmpty())
{
//出隊(duì)
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;
//產(chǎn)生新的狀態(tài)
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);
}
}
//狀態(tài)類
class Zt
{
//靜態(tài)容量
public static int[] rl = {9,7,4,2};
//記錄次數(shù)
int last;
//當(dāng)前狀態(tài)
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值是不是存在當(dāng)前狀態(tài)
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瓶的空閑量
//建立新的狀態(tài)
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的剩余量，倒?jié)Mj后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);
}
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
