题目描述

BFS或DFS
本质上就是遍历图，边遍历边找新状态

DFS

import java.util.*;

class Main {
    static final int N = 21;

    static int A, B, C;
    static boolean[][][] st = new boolean[N][N][N];
    static int[] W;
    static void dfs(int a, int b, int c) {

        //如果这个状态被搜过就返回
        if (st[a][b][c]) return;

        //状态设为true
        st[a][b][c] = true;

        //选择哪个桶
        for (int i = 0; i < 3; i++) {
            //倒入那个桶
            for (int j = 0; j < 3; j++) {
                if (i != j) {// 从桶i往桶j中倒
                    int[] w = {a, b, c};
                    // r代表可以倒的量
                    int r = Math.min(w[i], W[j] - w[j]);
                    w[i] -= r;
                    w[j] += r;

                    int k = w[0], q = w[1], l = w[2];
                    // 如果当前状态没被搜过
                    if (!st[k][q][l]) {
                        dfs(k, q, l); //递归调用深度优先搜索
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        A = scanner.nextInt();
        B = scanner.nextInt();
        C = scanner.nextInt();

        W = new int[]{A , B , C}; 

        dfs(0, 0, C);

        for (int c = 0; c <= C; c++) {
            for (int b = 0; b <= B; b++) {
                if (st[0][b][c]) {
                    System.out.print(c + " ");
                }
            }
        }
    }
}

BFS

import java.util.*;

class Main {
    static class Node {
        int a, b, c;

        public Node(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static final int N = 21;
    static final int M = N * N * N;

    static int A, B, C;

   //表示这个点有没有被搜过
    static boolean[][][] st = new boolean[N][N][N];
   //三元组(用数组模拟队列)
    static Node[] q = new Node[M];

    static void bfs() {
        //hh队头 tt队尾
        int hh = 0, tt = 0;
        //初始状态
        q[0] = new Node(0, 0, C);
        //初始状态设为true
        st[0][0][C] = true;
        //桶的容量
        int[] W = {A, B, C};

        while (hh <= tt) {
            //取队头元素
            Node t = q[hh++];
            //选择哪个桶
            for (int i = 0; i < 3; i++) {
                //倒入那个桶
                for (int j = 0; j < 3; j++) {
                    if (i != j) {  // 从桶i往桶j中倒
                        int[] w = {t.a, t.b, t.c};
                        //r代表可以倒的量
                        int r = Math.min(w[i], W[j] - w[j]);
                        w[i] -= r;
                        w[j] += r;

                        int a = w[0], b = w[1], c = w[2];
                        //如果当前状态没被搜过
                        if (!st[a][b][c]) {
                            //当前状态设为true
                            st[a][b][c] = true;
                            //放入队尾
                            q[++tt] = new Node(a, b, c);
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        A = scanner.nextInt();
        B = scanner.nextInt();
        C = scanner.nextInt();

        bfs();

        for (int c = 0; c <= C; c++) {
            for (int b = 0; b <= B; b++) {
                if (st[0][b][c]) {
                    System.out.print(c + " ");
                }
            }
        }
    }
}