Java数据结构（倒水问题）

倒水问题

题目描述
聪聪有三个水杯，它们的容积刚好为 n，x 和 y （1≤n,x,y≤100）。
今天灵灵来到聪聪家里面做客，于是聪聪就拿着容量为 n 的那个水杯去集市上接了满满一杯西瓜汁回来。
聪聪想要把 n 体积的西瓜汁平分成相等的两份。
聪聪每次可以选择两个杯子（我们这里假设是杯子a和杯子b），然后将杯子a中的西瓜汁倒入杯子b中。
每一轮倒水过程会一直进行，直到满足下述两种情况之一才会结束：
杯子a中的西瓜汁全部导入了杯子b中；
杯子b满了。
聪聪想知道，他最少需要几步，才能将体积为 n 的西瓜汁平分到两个杯子中。

思路：求最少次数，本题可以用bfs来做。储存进入队列的是每个杯子当前的状态。当然，每个状态是否出现过，我们用一个数组储存记录就好了。每种状态最多可以拓展6种情况。

import java.util.LinkedList; import java.util.Scanner; /**
 * @Author Fu XvZhuang
 * @Date 2020/8/13 8:00
 * @Version 1.0
 */ public class Main { static int n,x,y,ans; static int[][][] book = new int[105][105][105]; static LinkedList<Node> linkedList = new LinkedList<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); x = sc.nextInt(); y = sc.nextInt(); if(n%2==1){ System.out.println("-1"); System.exit(0); } bfs(); if(ans==0){ System.out.println("-1"); }else { System.out.println(ans); } } public static void bfs(){ Node n1 = new Node(); n1.a = n; n1.b = 0; n1.c = 0; n1.s = 0; book[n][x][y]=1; linkedList.addLast(n1); while(linkedList.size()>0){ Node  frist = linkedList.getFirst(); linkedList.remove(0); if(ok(frist)){ ans = frist.s; return ; } if(frist.a!=0&&frist.b!=x){ // 1->2 1里面有水并且2没有满 Node temp = new Node(); if(frist.a>x-frist.b){ temp.b = x; temp.a = frist.a-(x-frist.b); }else { temp.a = 0; temp.b = frist.a+frist.b; } temp.c = frist.c; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } if(frist.a!=0&&frist.c!=y) { //1->3 Node temp = new Node(); if(frist.a>y-frist.c){ temp.c = y; temp.a = frist.a-(y-frist.c); }else { temp.a = 0; temp.c = frist.a+frist.c; } temp.b = frist.b; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } if(frist.b!=0&&frist.a!=n){ // 2->1 Node temp = new Node(); if(frist.b>n-frist.a){ temp.a = n; temp.b = frist.b - (n-frist.a); }else { temp.b = 0; temp.a = frist.a+frist.b; } temp.c = frist.c; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } if(frist.b!=0&&frist.c!=y){ //2->3 Node temp = new Node(); if(frist.b>y-frist.c){ temp.c = y; temp.b = frist.b - (y-frist.c); }else { temp.b = 0; temp.c = frist.c+frist.b; } temp.a = frist.a; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } if(frist.c!=0&&frist.a!=n){ //3->1 Node temp = new Node(); if(frist.c>n-frist.a){ temp.a = n; temp.c = frist.c - (n-frist.a); }else { temp.c = 0; temp.a = frist.a+frist.c; } temp.b = frist.b; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } if(frist.c!=0&&frist.b!=x){ //3->2 Node temp = new Node(); if(frist.c>x-frist.b){ temp.b = x; temp.c = frist.c - (x-frist.b); }else { temp.c = 0; temp.b = frist.b+frist.c; } temp.a = frist.a; temp.s = frist.s+1; if(book[temp.a][temp.b][temp.c]==0) linkedList.addLast(temp); book[temp.a][temp.b][temp.c] = 1; } } } public static boolean ok(Node node){ if(node.a==node.b&&n/2==node.a) return true; if(node.a==node.c&&n/2==node.a) return true; if(node.b==node.c&&n/2==node.b) return true; return false; } } class Node{ int a,b,c,s; } 

本文地址：https://blog.csdn.net/guyjy/article/details/108025143