package oil;

public class DistrOil {

	private static int cnum=1000;	//初始化數(shù)組的大小
	
	static int[][] oilData = new int[cnum][4]; //oilData[cnum][0]表示父節(jié)點在數(shù)組中的位置
										//oilData[cnum][1]第一瓶油的數(shù)量
										//oilData[cnum][2]第二瓶油的數(shù)量
										//oilData[cnum][3]第三瓶油的數(shù)量
	
	//判斷數(shù)據(jù)是否已經(jīng)存在
	private static boolean isExistData(int x, int y, int z){
		boolean lpBool = false;
		for(int i=0; i<=cnum; i++){
			if(oilData[i][1]==x && oilData[i][2]==y && oilData[i][3]==z){
				lpBool=true;
				break;
			}
		}
		return lpBool;
	}
	
	//判斷數(shù)據(jù)是否是目標結(jié)點
	private static boolean isAimData(int n){
		boolean lpBool = false;
			if(oilData[n][1]==5 && oilData[n][2]==5 && oilData[n][3]==0){
				lpBool=true;
			}
		return lpBool;
	}

//	把新數(shù)據(jù)插入到數(shù)組中
	private static void addData(int x, int y, int z, int fatherNo){
		cnum++;
		oilData[cnum][0]=fatherNo;
		oilData[cnum][1]=x;
		oilData[cnum][2]=y;
		oilData[cnum][3]=z;
	}

	//根據(jù)規(guī)則進行分油，產(chǎn)生新的子節(jié)點數(shù)據(jù)
	private static void distrOilByRule(int n){
		int x=0,y=0,z=0,x1=0,y1=0,z1=0;
		x=oilData[n][1];
		y=oilData[n][2];
		z=oilData[n][3];
		if(z>0){
			x1=x+z; y1=y; z1=0;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}
		if(y>0){
			x1=x+y; y1=0; z1=z;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}		
		if(x>0&&y<7){
			x1=x+y-7; y1=7; z1=z;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}
		if(x>0&&z<3){
			x1=x+z-3; y1=y; z1=3;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}		
		if(y>0&&y+z<3){
			x1=x; y1=0; z1=y+z;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}
		if(z>0&&y+z<7){
			x1=x; y1=y+z; z1=0;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}
		if(z>0&&y<7&&z+y>=7){
			x1=x; y1=7; z1=z+y-7;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}
		if(y>0&&z<3&&y+z>=3){
			x1=x; y1=y+z-3; z1=3;
			if(!isExistData(x1,y1,z1)){
				addData(x1,y1,z1,n);
			}
		}		

	}

	//按遞歸方式進行分油,并返回最終結(jié)果在數(shù)組中的位置
	private static int distrOil(int n){
		if(isAimData(n)){
			return n;
		}else{
			distrOilByRule(n);
//			System.out.println("");
//			for(int i=0; i<cnum; i++){
//				System.out.print("-->");
//				System.out.print("("+oilData[i][1]+","+oilData[i][2]+","+oilData[i][3]+")");
//			}
			n++;
			return distrOil(n);
		}
			
	}

	public static void main(String[] args) {
		int endNode=0, i=0;
		cnum=0;
		oilData[0][0]=0;
		oilData[0][1]=10;
		oilData[0][2]=0;
		oilData[0][3]=0;
		endNode=distrOil(cnum);
		int[] aimVec = new int[cnum];
		while(endNode!=0){
			aimVec[i]=endNode;
			endNode=oilData[endNode][0];
			i++;
		}
		System.out.println("分油最終路徑為：");
		System.out.print("("+oilData[0][1]+","+oilData[0][2]+","+oilData[0][3]+")");
		for(int j=i-1; j>=0; j--){
			System.out.print("-->");
			System.out.print("("+oilData[aimVec[j]][1]+","+oilData[aimVec[j]][2]+","+oilData[aimVec[j]][3]+")");
		}
	}

}