leetcode-go/poj/3278.catch-that-cow/Test.java

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Test {
  private static final int MAXN = 100000;
  private static boolean[] used = new boolean[MAXN + 1];
  private static Queue<Integer> queue = new LinkedList<Integer>();

  public static void main(String[] args) throws IOException{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    String s;
    int N, K;
    while ((s = in.readLine()) != null) {
      String[] nk = s.split("\\s+");
      N = Integer.parseInt(nk[0]);
      K = Integer.parseInt(nk[1]);
      out.println(catchCow(N, K));
    }
    out.flush();
  }

  private static int catchCow(int N, int K) {
    queue.clear();
    Arrays.fill(used, false);
    queue.offer(N);
    used[N] = true;
    int size = queue.size(), cnt = 0;
    while (size != 0) {
      int i = queue.poll();
      size--;
      if (i == K) break;
      if (i - 1 >= 0 && !used[i - 1]) {
        queue.offer(i - 1);
        used[i - 1] = true;
      }
      if (i + 1 <= MAXN && !used[i + 1]) {
        queue.offer(i + 1);
        used[i + 1] = true;
      }
      if (i * 2 <= MAXN && !used[i * 2]) {
        queue.offer(i * 2);
        used[i * 2] = true;
      }
      if (size == 0) {
        size = queue.size();
        cnt++;
      }
    }
    return cnt;
  }
}