三个水杯_ny_21(广搜).java - JAVA

三个水杯

时间限制：1000 ms | 内存限制：65535 KB 难度：4

描述

给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。

输入

第一行一个整数N(0 接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态

输出

每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1

样例输入

样例输出

3
-1

来源

经典题目

上传者

hzyqazasdf

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{//广搜
	static int sa,sb,sc,ea,eb,ec;
	static boolean vis[][][];//标记当前水的数量是否出现过
	static Queue
      
        queue=null;
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int N=input.nextInt();
		while(N-->0){
			Init(input);
			if(ea+eb+ec!=sa){//开始状态和最终状态水的数量相同
				System.out.println(-1);
				continue;
			}
			F f=new F(sa,0,0);//开始初始化，第一杯水满，第二第三水为空
			f.sum=0;//初始化操作次数为零
			vis=new boolean[sa+5][sb+5][sc+5];
			vis[sa][0][0]=true;//标记当前
			queue=new LinkedList
       
        (); queue.add(f); System.out.println(bfs(queue)); } } private static int bfs(Queue
        
          q) {//广搜 while(!q.isEmpty()){ F f=q.poll(); if(f.a[0]==ea&&f.a[1]==eb&&f.a[2]==ec){ return f.sum; } int[] s=f.copy(); if(s[0]>0&&s[1]
         
          0&&s1[2]
          
           0&&s2[0]
           
            0&&s3[2]
            
             0&&s4[0]
             
              0&&s5[1]