广搜——三个水杯

快来打我* 2022-08-21 00:03 167阅读 0赞

三个水杯
    时间限制：1000 ms  |  内存限制：65535 KB
    难度：4
    描述
    给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根
    据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
    输入
    第一行一个整数N(0<N<50)表示N组测试数据
    接下来每组测试数据有两行，第一行给出三个整数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

注意广搜过程中的节点的状态的确立，对于复杂的状态需要封装成一个类表示。此外，广搜为实现由近及远的搜索，需要使用一个标记数组将访问过的状态存储起来。  
广搜由于按照距开始状态由近及远的顺序搜索，所以可以很容易的用来求最短路径、最少操作之类问题的答案。

这道题根据题意描述出水杯倒水过程，可以很容易的得到状态迁移二叉树，这里的状态包含：当前三个水杯的状态数组state，到达当前状态所需的次数step。

尤其要注意的是这里将各个过程的分解方式，不是一股脑的写在一起！  
同时还要注意的一个小技巧是：对于从下标0开始存储的有n个元素的数组，如果取出i(0<=i

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    class Cup{
        int[] state = new int[3];
        int step = 0;
        public Cup(int first,int second,int third,int s) {
            // TODO Auto-generated constructor stub
            this.state[0] = first;
            this.state[1] = second;
            this.state[2] = third;
            this.step = s;
        }
        public Cup(Cup cope){
            for(int i=0;i<3;i++) this.state[i] = cope.state[i];
            this.step = cope.step;
        }
    }
    
    public class Main {
    
        static boolean DEBUG = false;
        static boolean[][][] visited = new boolean[100][100][100];
        static Queue<Cup> que = new LinkedList<Cup>();
        static int[] cupCapacity = new int[3],targetCapacity = new int[3];
        static Cup cur,next;
    
        static void test(){
            System.out.println("breakpoint!");
        }
        static boolean isEqual(Cup p){
            for(int i=0;i<3;i++){
                if(p.state[i]!=targetCapacity[i]) return false;
            }
            return true;
        }
        static Cup pour(Cup p,int x,int y){
       // x -> y
            Cup ret = new Cup(p);
            int need = cupCapacity[y] - p.state[y];
            //其中必有个杯子要么满，要么空！
            if(need<=p.state[x]){
       // x 中水足够
                ret.state[x] -= need;
                ret.state[y] += need;
            }
            else{
       // x中的水不足,将x中的水全部倒入y
                ret.state[x] = 0;
                ret.state[y] += p.state[x];
            }
            return ret;
        }
        static int BFS(){
            Cup first = new Cup(cupCapacity[0],0,0,0);
            visited[cupCapacity[0]][0][0] = true;
            que.offer(first);
            while(!que.isEmpty()){
                if(DEBUG) test();
                cur = que.remove();
                if(isEqual(cur)) return cur.step;
                else{
                    for(int i=0;i<3;i++){
                        for(int j=1;j<3;j++){
                            int k = (i+j)%3;
                            // 从第i个水杯向第k个水杯倒水：第i个水杯有水且第k个水杯有余量
                            if(cur.state[i]!=0&&cur.state[k]<cupCapacity[k]){
                                next = pour(cur, i, k);
                                if(!visited[next.state[0]][next.state[1]][next.state[2]]){
                                    visited[next.state[0]][next.state[1]][next.state[2]] = true;
                                    next.step = cur.step + 1;
                                    que.offer(next);
                                }
                            }
                        }
                    }
                }
            }
            return -1;
        }
        static void init(){
            for(int i=0;i<100;i++){
                for(int j=0;j<100;j++){
                    for(int k=0;k<100;k++) visited[i][j][k] = false;
                }
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int N = in.nextInt();
                while((N--)>0){
                    que.clear();
                    for(int i=0;i<3;i++) cupCapacity[i] = in.nextInt();
                    for(int i=0;i<3;i++) targetCapacity[i] = in.nextInt();
                    init();
                    int ret = BFS();
                    System.out.println(ret);
                }
            }
        }
    
    }

体会：  
编程时，不论是方法、变量、过程，都应做到所见即所得，一目了然，应将冗余的代码片整合为一个方法或函数，然后进行调用，虽然在当时看来，有些麻烦，没有必要，但从长远看来，这样做不仅有利于理清思路，更有利于调试程序。不过尤其要注意的一点是，方法的传参问题，传递的是一个数值，还是存储数值的变量引用，返回的是什么，即各片段间的“无缝接合”。