distroil.java

两个小孩去打油

package oil;

public class DistrOil {

	private static int cnum=1000;	//初始化数组的大小
	
	static int[][] oilData = new int[cnum][4]; //oilData[cnum][0]表示父节点在数组中的位置
										//oilData[cnum][1]第一瓶油的数量
										//oilData[cnum][2]第二瓶油的数量
										//oilData[cnum][3]第三瓶油的数量
	
	//判断数据是否已经存在
	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;
	}
	
	//判断数据是否是目标结点
	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;
	}

//	把新数据插入到数组中
	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;
	}

	//根据规则进行分油，产生新的子节点数据
	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);
			}
		}		

	}

	//按递归方式进行分油,并返回最终结果在数组中的位置
	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]+")");
		}
	}

}