现在的位置: 首页 > 综合 > 正文

ACM_21三个水杯

2019年06月14日 ⁄ 综合 ⁄ 共 6447字 ⁄ 字号 小 中 大 ⁄ 评论关闭

三个水杯

时间限制：1000 ms
 |  内存限制：65535 KB
难度：4
描述
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
输入
第一行一个整数N(0
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100
V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态
输出
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
样例输入

2 

6 3 1 

4 1 1 

9 3 2 

7 1 1
样例输出

3
-1
来源

经典题目
上传者
hzyqazasdf
分析 按照树的广度遍历
这是WA掉的代码 ，但是网上找到的测试数据都成功了，自己debug也没发现异常流程

import
java.util.ArrayList;
import
java.util.Scanner;

//WA
public
class Three_cups {

public
static void main(String[] args) {
     
  Three_cups three_cups  = new
Three_cups();
     
  three_cups.solution();
}

public
void solution() {
Scanner in = new Scanner(System.in);
int
groups = in.nextInt();
for
(int i = 0; i < groups; i++) {
     
     Item source
= new
Item(in.nextInt(),in.nextInt(),in.nextInt(),0);//存取水杯大小
     
     Item
initial = new Item(source.cups[0],0,0,0);//构建根节点
     
     Item target
= new
Item(in.nextInt(),in.nextInt(),in.nextInt(),Integer.MAX_VALUE);
     
   
 //构建目标节点
     
     ArrayList
 queue = new ArrayList();//以队列形式保存树的结构
     
   
 queue.add(initial);
     
     int pointer
= 0;//指向下一个应该被检索的节点
     
     int result
= -1;//保存结果
     
   
 while(pointer < queue.size()){
     
    Item temp =
queue.get(pointer); //存取temp1的父节点的水杯装快
     
    Item temp1;
  //用来标注新生成的水杯状态
     
    int tempA;
     
    int tempB;
     
    int tempC;
     
    //水杯A 向B C 注水
     
    if(temp.cups[0] !=
0){
     
    tempB =
Math.min(temp.cups[0]+temp.cups[1],source.cups[1]);
     
    tempA =
temp.cups[0]+temp.cups[1] - tempB;
     
    tempC =
temp.cups[2];
     
    temp1 = new Item( tempA,tempB
,tempC, temp.mark+1);
     
    //检查是否达到目标情况
如果没有则压入树
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    
     
    tempC =
Math.min(temp.cups[0]+temp.cups[2],source.cups[2]);
     
    tempA =
temp.cups[0]+temp.cups[2] - tempC;
     
    tempB =
temp.cups[1];
     
    temp1 = new Item( tempA,tempB
,tempC, temp.mark+1);
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    }
     
    //水杯B向A C 注水
     
    if(temp.cups[1] !=
0){
     
    tempA =
Math.min(temp.cups[0]+temp.cups[1],source.cups[0]);
     
    tempB =
temp.cups[0]+temp.cups[1] - tempA;
     
    tempC =
temp.cups[2];
     
    temp1 = new Item( tempA,tempB
,tempC, temp.mark+1);
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    
     
    tempC =
Math.min(temp.cups[1]+temp.cups[2],source.cups[2]);
     
    tempB =
temp.cups[1]+temp.cups[2] - tempC;
     
    tempA =
temp.cups[0];
     
    temp1 = new Item( tempA,tempB
,tempC, temp.mark+1);
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    }
     
    //水杯C 向 A B 中注水
     
    if(temp.cups[2] !=
0){
     
    tempA =
temp.cups[0];
     
    tempB =
Math.min(temp.cups[2]+temp.cups[1],source.cups[1]);
     
    tempC =
temp.cups[2]+temp.cups[1] - tempB;
     
    temp1 = new Item( tempA
,tempB ,tempC, temp.mark+1);
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    
     
    tempA =
Math.min(temp.cups[0]+temp.cups[2],source.cups[0]);
     
    tempB =
temp.cups[1];
     
    tempC =
temp.cups[0]+temp.cups[2] - tempA;
     
    temp1 = new Item( tempA,tempB
,tempC, temp.mark+1);
     
   
if(temp1.equals(target)){
     
    result =
temp1.mark;
     
    break;
     
    }
     
   
if(!queue.contains(temp1)){
     
    queue.add(temp1);
     
   
System.out.println(temp1.cups[0]+" "+temp1.cups[1]+"
"+temp1.cups[2]+" "+temp1.mark);
     
    }
     
    }
     
    pointer++;//检查完当前节点
指针移动
     
   
 }
     
   
 
     
   
 System.out.println(result);
} 
}
//节点
 保存信息 A B C 中水的数量， 已经倒过的次数
class
Item{
int[]
cups;
int
mark;
public
Item(int A ,int B ,int C ,int mark){
cups
=new int[3];
cups[0] = A;
cups[1] = B;
cups[2] = C;
this.mark = mark;
}
@Override
public
boolean equals(Object o) {
//
TODO Auto-generated method stub
if
((cups[0] == ((Item) o).cups[0]) && (cups[1] == ((Item)
o).cups[1])
&& (cups[2] == ((Item)o).cups[2])) {
return
true;
}
return
false;
}
}
}
这是A掉的 借鉴了别人的代码， 算法完全一样 不知道是哪里出了问题
package practise;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Three_cups_C{//广搜
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]
s[1] = Math.min(f.a[0]+f.a[1],sb );
s[0] = f.a[0]+f.a[1] - s[1];
if(!vis[s[0]][s[1]][s[2]]){
F g=new F(s[0],s[1],s[2]);
g.sum=f.sum+1;
q.add(g);
vis[s[0]][s[1]][s[2]]=true;
}
}
int[] s1=f.copy();
if(s1[0]>0&&s1[2]
s1[2] = Math.min(f.a[0]+f.a[2],sc );
s1[0] = f.a[0]+f.a[2] - s1[2];
if(!vis[s1[0]][s1[1]][s1[2]]){
F g=new F(s1[0],s1[1],s1[2]);
g.sum=f.sum+1;
q.add(g);
vis[s1[0]][s1[1]][s1[2]]=true;
}
}
int[] s2=f.copy();
if(s2[1]>0&&s2[0]
s2[0] = Math.min(f.a[0]+f.a[1],sa );
s2[1] = f.a[0]+f.a[1] - s2[0];
if(!vis[s2[0]][s2[1]][s2[2]]){
F g=new F(s2[0],s2[1],s2[2]);
g.sum=f.sum+1;
q.add(g);
vis[s2[0]][s2[1]][s2[2]]=true;
}
}
int[] s3=f.copy();
if(s3[1]>0&&s3[2]
s3[2] = Math.min(f.a[1]+f.a[2],sc );
s3[1] = f.a[1]+f.a[2] - s3[2];
if(!vis[s3[0]][s3[1]][s3[2]]){
F g=new F(s3[0],s3[1],s3[2]);
g.sum=f.sum+1;
q.add(g);
vis[s3[0]][s3[1]][s3[2]]=true;
}
}
int[] s4=f.copy();
if(s4[2]>0&&s4[0]
s4[0] = Math.min(f.a[0]+f.a[2],sa );
s4[2] = f.a[0]+f.a[2] - s4[0];
if(!vis[s4[0]][s4[1]][s4[2]]){
F g=new F(s4[0],s4[1],s4[2]);
g.sum=f.sum+1;
q.add(g);
vis[s4[0]][s4[1]][s4[2]]=true;
}
}
int[] s5=f.copy();
if(s5[2]>0&&s5[1]
s5[1] = Math.min(f.a[1]+f.a[2],sb );
s5[2] = f.a[1]+f.a[2] - s5[1];
if(!vis[s5[0]][s5[1]][s5[2]]){
F g=new F(s5[0],s5[1],s5[2]);
g.sum=f.sum+1;
q.add(g);
vis[s5[0]][s5[1]][s5[2]]=true;
}
}
}
return -1;
}
private static void Init(Scanner input) {//初始化输入
sa=input.nextInt();
sb=input.nextInt();
sc=input.nextInt();
ea=input.nextInt();
eb=input.nextInt();
ec=input.nextInt();
}
}
class F{//存当前三个水杯的水数量
int a[];
int sum;
public F(int a1, int a2, int a3) {
a=new int[3];
this.a[0] = a1;
this.a[1] = a2;
this.a[2] = a3;
}
public int[] copy(){
int s[]=new int[a.length];
for(int i=0;i
s[i]=a[i];
return s;
}
F(){}
} 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞