十三 1355. 母亲的牛奶 (BFS)

1355. 母亲的牛奶 (BFS)

思路：使用BFS搜索所有可能出现的情况，同时保存到used数组，防止重复搜索，最后遍历used数组，因为只求C桶中牛奶，所有先遍历C桶，出现A桶为空立即打印结果并break。

import java.util.*;

public class Main {
    private static int A, B, C;
    private static int[] T;
    private static boolean[][][] used;
    
    private static void bfs() {
        used = new boolean[A + 1][B + 1][C + 1];
        used[0][0][C] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, C});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i != j) {
                        int[] t = new int[]{temp[0], temp[1], temp[2]};
                        int n = Math.min(t[i], T[j] - t[j]);
                        t[i] -= n;
                        t[j] += n;
                        if (!used[t[0]][t[1]][t[2]]) {
                            used[t[0]][t[1]][t[2]] = true;
                            queue.offer(t);
                        }
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        T = new int[]{A, B, C};
        bfs();
        for (int c = 0; c <= C; c++) {
            for (int b = 0; b <= B; b++) {
                if (used[0][b][c]) {
                    System.out.print(c + " ");
                    break;
                }
            }
        }
    }
}