HDU 1495 非常可樂

非常可樂
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3570 Accepted Submission(s): 1469

Problem Description
大家一定覺的運動以後喝可樂是一件很惬意的事情，但是seeyou卻不這麼認為。因為每次當seeyou買了可樂以後，阿牛就要求和seeyou一起分享這一瓶可樂，而且一定要喝的和seeyou一樣多。但seeyou的手中只有兩個杯子，它們的容量分別是N 毫升和M 毫升 可樂的體積為S （S<101）毫升　(正好裝滿一瓶) ，它們三個之間可以相互倒可樂 (都是沒有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聰明的ACMER你們說他們能平分嗎？如果能請輸出倒可樂的最少的次數，如果不能輸出"NO"。

Input
三個整數 : S 可樂的體積 , N 和 M是兩個杯子的容量，以"0 0 0"結束。

Output
如果能平分的話請輸出最少要倒的次數，否則輸出"NO"。

Sample Input
7 4 3
4 1 3
0 0 0

Sample Output
NO
3

import java.io.*;
import java.util.*;
class Node{
	int max[];
	int v[];
	int count;
	Node(){
		max=new int[3];
		v=new int[3];
		count=0;
	}
	public Node getNode(){
		Node node=new Node();
		for(int i=0;i<3;i++){
			node.max[i]=max[i];
			node.v[i]=v[i];
		}
		node.count=count;
		return node;
	}
}
/*
 * @author denghuilong 
 *  
 * 2013-8-13下午4:14:49
 *
*/
public class Main {
	public boolean boo[]=new boolean[100*100*100+100*100+100];
	public Queue<Node> list=new LinkedList<Node>();
	public static void main(String[] args) {
		new Main().work();
	}
	public void work(){
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNextInt()){
			Arrays.fill(boo, false);
			list.clear();
			int s=sc.nextInt();
			int m=sc.nextInt();
			int n=sc.nextInt();
			if(s==0&&m==0&&n==0)
				System.exit(0);
			Node node=new Node();
			node.max[0]=s;
			node.max[1]=m;
			node.max[2]=n;
			node.v[0]=node.max[0];
			node.count=0;
			list.add(node);
			BFS();
		}
	}
	public  void BFS(){
		while(list.size()!=0){
			Node node=list.poll();
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(i==j||node.max[j]==node.v[j])
						continue;
					Node t=node.getNode();
					t.count++;
					if(t.v[i]>=(t.max[j]-t.v[j])){
						t.v[i]=t.v[i]-(t.max[j]-t.v[j]);
						t.v[j]=t.max[j];
					}
					else{
						t.v[j]=t.v[i]+t.v[j];
						t.v[i]=0;
					}
					int step=getStep(t);
					if(!boo[step]){
						if(check(t)){
							System.out.println(t.count);
							return;
						}
						boo[step]=true;
						list.add(t);
					}
				}
			}
		}
		System.out.println("NO");
	}
	public  int getStep(Node node){
		return node.v[0]*100*100+node.v[1]*100+node.v[2];
	}
	public boolean check(Node node){
		int s=node.v[0];
		int m=node.v[1];
		int n=node.v[2];
		if((s==m&&n==0)||(s==n&&m==0)||(s==0&&n==m))
			return true;
		return false;
	}
}