[白俊]#14867バケツ

30532 ワード
白駿 BFS algorithm テキストリンク

質問する


容量の異なる空きバケツA、Bが2つあります.これらのバケツに水をいっぱい入れて、空っぽの作業を繰り返して、2つのバケツを所望の状態(目標量の水が入っている)にしたいと思っています.バケツ以外では正確に水量を測ることができず、可能な作業は以下の3つしかありません.
  • [F(x):Fillx]:バケツxを水で満たします.(水が満杯になるまで、バケツxが空いているかどうかにかかわらず、他のバケツはそのまま)
    • .
  • [E(x):Empty x]:バケツxの水を全部捨てる.
  • [M(x,y):Move water from x to y]:バケツxの水をバケツyに注ぐ.このとき、バケツxに残った水量がバケツyに残った空隙以下であれば、バケツxに残った水を全てバケツyに注ぐ.バケツxに残っている水の量がバケツyに残っている隙間より多い場合は、いくらでも注いで、バケツyをいっぱいにして、残りはバケツxに残しておくことができます.
    • 例えば、バケツA及びBの容量は、それぞれ2リットル及び5リットルである.2つのバケツがいずれも空の状態から始まり、最終的にバケツAに2リットルの水を残し、バケツBに4リットルの水を残したい場合は、以下の手順で操作を行い、合計8回の操作を行い、所望の状態に達することができる.
    (0,0)→[F(B)]→(0,5)→[M(B,A)]→(2,3)→[E(A)]→(0,3)→[M(B,A)]→(2,1)→[E(A)]→(0,1)→[M(B,A)]→(1,0)→[F(B)]→(1,5)→[M(B,A)]→(2,4)
    ただし、以下の手順で操作を行うと、必要な操作総数は5回となる.
    (0,0)→[F(A)]→(2,0)→[M(A,B)]→(0,2)→[F(A)]→(2,2)→[M(A,B)]→(0,4)→[F(A)]→(2,4)
    2つのバケツの容量と必要な最終状態を入力した後、1つのプログラムを作成し、2つのバケツが空の状態にあることから、最終状態に達するために必要な最小操作数を求める.

    入力


    1つの整数a(1≦a<100000)、1つの整数a(1≦a<100000)、1つの整数b(a

    しゅつりょく


    目標状態に達した最小タスク数を示す整数を標準出力として出力します.ターゲット状態に達する方法がない場合は、-1を出力します.

    入力例1

    3 7 3 2

    サンプル出力1

    9

    入力例2

    2 5 0 1

    サンプル出力2

    5

    入力例3

    3 5 2 4

    サンプル出力3

    -1

    に答える


    この問題はbfs(幅優先探索)アルゴリズムで解くことができる.
    import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int max_a;
    static int max_b;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        max_a = Integer.parseInt(input[0]);
        max_b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);
        int d = Integer.parseInt(input[3]);

        bfs(c, d);
    }

    public static void bfs(int c, int d) {
        Queue<Pair> queue = new LinkedList<>();
        HashSet<Pair> visited = new HashSet<>();
        visited.add(new Pair(0, 0, 0));
        queue.add(new Pair(0, 0, 0));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.a==c && temp.b==d) {
                System.out.println(temp.cnt);
                return;
            }

            if(temp.a<max_a) {        //F(a)
                Pair p = new Pair(max_a, temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.b<max_b) {    //F(b)
                Pair p = new Pair(temp.a, max_b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a>0) {    //E(a)
                Pair p = new Pair(0, temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.b>0) {      //E(b)
                Pair p = new Pair(temp.a, 0, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a+temp.b<=max_a) {    //M(b, a)
                Pair p = new Pair(temp.a+temp.b, 0, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            else {
                Pair p = new Pair(max_a, temp.a+temp.b-max_a, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            if(temp.a+temp.b<=max_b) {    //M(a, b)
                Pair p = new Pair(0, temp.a+temp.b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }

            else {
                Pair p = new Pair(temp.a+temp.b-max_b, max_b, temp.cnt+1);

                if(!visited.contains(p)) {
                    visited.add(p);
                    queue.add(p);
                }
            }
        }

        System.out.println(-1);
    }

    public static class Pair {
        int a;
        int b;
        int cnt;

        public Pair(int a, int b, int cnt) {
            this.a = a;
            this.b = b;
            this.cnt = cnt;
        }
        
        /////////중복 확인을 위한 메소드 
        
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair) o;

            return (p.a == this.a && p.b == this.b);
        }

        @Override
        public int hashCode() {
            return (""+a+b).hashCode();
        }
    }
}
    [TIL]CLTと信頼区間
    HTML 1.タグ(Tag)