又是深度優(yōu)先搜索，枚舉，為了不出現(xiàn)無限循環(huán)，為了所出現(xiàn)的每種狀態(tài)（三個杯子現(xiàn)有milk數(shù)）僅考慮一次，使用isAppeared變量來記錄某種狀態(tài)是否已經(jīng)出現(xiàn)過。

?

Code
/**//*
ID:?sdjllyh1
PROG:?milk3
LANG:?JAVA
complete?date:?2008/11/22
author:?LiuYongHui?From?GuiZhou?University?Of?China
more?article:?www.cnblogs.com/sdjls
*/

import?java.io.*;
import?java.util.*;

public?class?milk3
{
????private?static?Cup[]?cup?=?new?Cup[3];
????private?static?ArrayList?answers?=?new?ArrayList();
????private?static?boolean[][][]?isAppeared;//記錄某種狀態(tài)是否出現(xiàn)過，避免沒有必要的遞歸搜索
????
????public?static?void?main(String[]?args)?throws?IOException
????{
????????init();
????????run();
????????output();
????????System.exit(0);
????}

????private?static?void?run()
????{
????????//一開始，把c往a里到
????????dfs_pour(cup[2],?cup[0]);
????????
????????//還原為初始狀態(tài)
????????cup[0].existing?=?0;
????????cup[1].existing?=?0;
????????cup[2].existing?=?cup[2].capacity;
????????//把c往b里到
????????dfs_pour(cup[2],?cup[1]);
????????//按照杯子里擁有的milk數(shù)進(jìn)行排序
????????Collections.sort(answers);
????}

????//把firstCup里的milk往secondCup里到，然后進(jìn)行深度優(yōu)先搜索
????private?static?void?dfs_pour(Cup?firstCup,?Cup?secondCup)
????{
????????firstCup.pour(secondCup);
????????//如果這個狀態(tài)出現(xiàn)過則退出遞歸，不再考慮
????????if?(isAppeared[cup[0].existing][cup[1].existing][cup[2].existing])
????????{
????????????return;
????????}
????????else
????????{
????????????//標(biāo)記已經(jīng)出現(xiàn)過此狀態(tài)
????????????isAppeared[cup[0].existing][cup[1].existing][cup[2].existing]?=?true;
????????????
????????????if?(cup[0].existing==0)
????????????{
????????????????answers.add(cup[2].cloneCup());
????????????}
????????????
????????????//給當(dāng)前杯子狀態(tài)做個備份
????????????Cup[]?backupCup?=?new?Cup[3];
????????????backupCup[0]?=?cup[0].cloneCup();
????????????backupCup[1]?=?cup[1].cloneCup();
????????????backupCup[2]?=?cup[2].cloneCup();

????????????//以下嘗試6種不同的傾倒方式
????????????dfs_pour(cup[0],?cup[1]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();

????????????dfs_pour(cup[0],?cup[2]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();

????????????dfs_pour(cup[1],?cup[0]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();

????????????dfs_pour(cup[1],?cup[2]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();

????????????dfs_pour(cup[2],?cup[0]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();

????????????dfs_pour(cup[2],?cup[1]);
????????????cup[0]?=?backupCup[0].cloneCup();
????????????cup[1]?=?backupCup[1].cloneCup();
????????????cup[2]?=?backupCup[2].cloneCup();
????????}
????}

????private?static?void?init()?throws?IOException
????{
????????BufferedReader?f?=?new?BufferedReader(new?FileReader("milk3.in"));
????????StringTokenizer?st?=?new?StringTokenizer(f.readLine());
????????int?capacityA?=?Integer.parseInt(st.nextToken());
????????int?capacityB?=?Integer.parseInt(st.nextToken());
????????int?capacityC?=?Integer.parseInt(st.nextToken());
????????f.close();
????????cup[0]?=?new?Cup(capacityA,?0);
????????cup[1]?=?new?Cup(capacityB,?0);
????????cup[2]?=?new?Cup(capacityC,?capacityC);
????????isAppeared?=?new?boolean[capacityA+1][capacityB?+?1][capacityC+1];
????}

????private?static?void?output()?throws?IOException
????{
????????PrintWriter?out?=?new?PrintWriter(new?BufferedWriter(new?FileWriter("milk3.out")));
????????Iterator?it?=?answers.iterator();
????????Cup?c?=?(Cup)it.next();
????????out.print(c.existing);
????????int?lastExisting?=?c.existing;//使用lastExisting是為了避免輸出相同的答案
????????while?(it.hasNext())
????????{
????????????c?=?(Cup)it.next();
????????????if?(lastExisting?!=?c.existing)
????????????{
????????????????out.print("?"?+?c.existing);
????????????????lastExisting?=?c.existing;????????????????????????
????????????}
????????}
????????out.println();
????????out.close();
????}
}

//杯子類
class?Cup?implements?Comparable
{
????public?int?capacity;//杯子的容量
????public?int?existing;//杯子當(dāng)前擁有的milk數(shù)
????public?Cup(int?capacity,int?existing)
????{
????????this.capacity?=?capacity;
????????this.existing?=?existing;
????}
????//向另一個杯子中傾倒milk
????public?void?pour(Cup?aim)
????{
????????if?(this.existing?>=?aim.capacity?-?aim.existing)
????????{
????????????this.existing?-=?aim.capacity?-?aim.existing;
????????????aim.existing?=?aim.capacity;
????????}
????????else
????????{
????????????aim.existing?+=?this.existing;
????????????this.existing?=?0;????????????
????????}
????}
????//獲得杯子的一個備份
????public?Cup?cloneCup()
????{
????????return?new?Cup(this.capacity,?this.existing);
????}
????//為了排序existing，以便輸出，而實(shí)現(xiàn)的
????public?int?compareTo(Object?arg0)
????{
????????Cup?compareCup?=?(Cup)arg0;
????????if?(this.existing?>?compareCup.existing)
????????{
????????????return?1;
????????}
????????else?if?(this.existing?<?compareCup.existing)
????????{
????????????return?-1;
????????}
????????else
????????{
????????????return?0;
????????}
????}
}

轉(zhuǎn)載于:https://www.cnblogs.com/SDJL/archive/2008/11/22/1339038.html

總結(jié)

以上是生活随笔為你收集整理的USACO_1_4_Mother's Milk的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。