正文
三个水杯——java,广度优先搜索
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目如下：
21-三个水杯
内存限制:64MB 时间限制:1000ms 特判: No
通过数:51 提交数:137 难度:4
题目描述:
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
输入描述:
第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态
第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态
输出描述:
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
样例输入:
复制
2
6 3 1
4 1 1
9 3 2
7 1 1
2
6 3 1
4 1 1
9 3 2
7 1 1
样例输出:
3
-1
3
-1
解题思想：题目不难，主要是捉住关键点就容易了，看到最少的倒水次数，必然和广度优先搜索有联系，其实就是一颗六叉树。
每个杯子都可以往其他两个杯子倒水。可以相互倒水，情况如下：1>2,1>3,2>1,2>3,3>1,3>2;
代码如下：用到了队列+广度的方法。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner; class State
{
int glass[] = new int[3];
int step;
}
public class Main
{
static final int MAX = 3;
static int v[] = new int[MAX];
static int e[] = new int[MAX];
static boolean vis[][][] = new boolean[300][300][300];
static int flag;
public static void main(String []args)
{
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 3; j++)
{
v[j] = cin.nextInt();
}
for(int j = 0; j < 3; j++)
{
e[j] = cin.nextInt();
}
flag = 0;
Init();
BFS();
if(flag == 0)
{
System.out.println("-1");
}
}
}
static void Init()
{
for(int i = 0; i < v[0]; i++)
{
for(int j = 0; j < v[0]; j++)
{
for(int k = 0; k < v[0]; k++)
{
vis[i][j][k] = false;
}
}
}
}
static void BFS()
{
State start = new State();
start.glass[0] = v[0];
start.glass[1] = 0;
start.glass[2] = 0;
if(start.glass[0] == e[0] && start.glass[1] == e[1] && start.glass[2] == e[2])
{
flag = 1;
System.out.println("0");
return;
}
Queue <State> que = new LinkedList<State>();
que.add(start);
vis[start.glass[0]][start.glass[1]][start.glass[2]] = true;
while(!que.isEmpty())
{
State temp = new State();
temp = que.poll();
for(int i = 0; i < 3; i++)//核心代码
{
if(temp.glass[i] == 0)
{
continue;
}
//i向j中倒水
for(int j = 0; j < 3; j++)
{
if(j == i || temp.glass[j] == v[j]) //同一个杯子或者这个杯子已经满了
{
continue;
}
//向其他某个杯子倒
State mid = new State();//此处的对象用得很巧妙（不可以定义在这个循环的外面），我之前都是建立一个很大很大的数组用来保存队列，太浪费空间了。
mid.glass[0] = temp.glass[0];
mid.glass[1] = temp.glass[1];
mid.glass[2] = temp.glass[2];
mid.step = temp.step+1;
int rest = v[j]-temp.glass[j];
if(rest <= mid.glass[i])
{
mid.glass[j] = v[j];
mid.glass[i] = mid.glass[i]-rest;
if(vis[mid.glass[0]][mid.glass[1]][mid.glass[2]] == false)
{
if(mid.glass[0] == e[0] && mid.glass[1] == e[1] && mid.glass[2] == e[2])
{
flag = 1;
System.out.println(mid.step);
return;
}
que.add(mid);
vis[mid.glass[0]][mid.glass[1]][mid.glass[2]] = true;
}
}
else
{
mid.glass[j] = mid.glass[j] + mid.glass[i];
mid.glass[i] = 0;
if(vis[mid.glass[0]][mid.glass[1]][mid.glass[2]] == false)
{
if(mid.glass[0] == e[0] && mid.glass[1] == e[1] && mid.glass[2] == e[2])
{
flag = 1;
System.out.println(mid.step);
return;
}
que.add(mid);
vis[mid.glass[0]][mid.glass[1]][mid.glass[2]] = true;
}
}
}
}
}
}
}
