阿祁的部落格

ZeroJudge e527 - 無刻度容器倒水問題 解題心得( 題目 )

解題概念:BFS

解題方法:窮舉每個組合

(註:機器人專題作業紀錄)

Java參考程式碼(有更好意見可留言於下方，謝謝!):

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class zje527 {
    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    public static int ret,rd;
    public static final int mod=998244353;
    public static boolean neg;
    public static Queue<Pair> q=new LinkedList<>();
    public static int[] cnt=new int[26];
    public static int[][] vis=new int[1030][1030];
     public static String[] st=new String[20];
    public static void main(String[] args) throws Exception{
        int t=readint();
        while(t-->0) {
            solve();
        }
        bw.flush();
    }
    
    public static void solve() throws Exception{
        final int m=readint();
        final int n=readint();
        final int g=readint();
        for(int i=0;i<vis.length;i++)Arrays.fill(vis[i],1<<29);
        vis[0][0]=0;
        q.offer(new Pair(0,0));
        Pair o;
        int cnt=0;
        while(!q.isEmpty()) {
            o=q.poll();
            cnt=vis[o.x][o.y];
            check(o.x,n,cnt);
            check(m,o.y,cnt);
            check(0,o.y,cnt);
            check(o.x,0,cnt);
            if(m-o.x>=o.y) {
                check(o.x+o.y,0,cnt);
            }
            else {
                check(m,o.y+o.x-m,cnt);
            }
            if(o.x<=n-o.y) {
                check(0,o.x+o.y,cnt);
            }
            else {
                check(o.y+o.x-n,n,cnt);
            }
        }
        int max=(1<<29);
        for(int i=0;i<=m;i++) {
            max=Math.min(max,vis[i][g]);
        }
        for(int i=0;i<=n;i++) {
            max=Math.min(max,vis[g][i]);
        }
        if(max==(1<<29)) {
            bw.write("-1\n");
            return;
        }
        bw.write(max+"\n");
    }
    
    public static void check(int x,int y,int idx) {
        if(vis[x][y]==(1<<29)) {
            vis[x][y]=idx+1;
            q.offer(new Pair(x,y));
        }
    }

    public static int readint() throws Exception{
        ret=0;
        rd=br.read();
        while(rd>47&&rd<58) {
            ret*=10;
            ret+=(rd&15);
            rd=br.read();
        }
        return ret;
    }
}


class Pair{
    int x,y;
    Pair(int a,int b){
        x=a;
        y=b;
    }
}