Breadth first search to catch cattle

One   Link to original question

3278 -- Catch That Cowhttp://poj.org/problem?id=3278

Two   Input and output

1  Input

Two Numbers , The first 1 The number represents the position of the farmer , The first 2 Number represents the position of cattle

2  Output

The minimum number of steps for a farmer to catch an ox

3、 ... and   Input and output examples

1  sample input

5 17

2  sample output

4

Four   Code

package graph.poj3278;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class POJ3278BFS {
    static final int MAXN = 100009;
    static boolean vis[] = new boolean[MAXN];
    static int d[] = new int[MAXN];
    static int n, k;

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

        if (k <= n) {
            System.out.println(n - k);
            return;
        }
        solve();
    }

    static void solve() {
        Queue<Integer> q = new LinkedList<>();
        vis[n] = true;
        d[n] = 0;
        q.add(n);
        while (!q.isEmpty()) {
            int u = q.peek();
            q.poll();
            if (u == k) {
                System.out.println(d[k]);
                return;
            }
            int x;
            x = u + 1;
            if (x >= 0 && x <= 100000 && !vis[x]) { //  Take a step forward 
                d[x] = d[u] + 1;
                vis[x] = true;
                q.add(x);
            }
            x = u - 1;
            if (x >= 0 && x <= 100000 && !vis[x]) { //  Take a step back 
                d[x] = d[u] + 1;
                vis[x] = true;
                q.add(x);
            }
            x = u * 2;
            if (x >= 0 && x <= 100000 && !vis[x]) { //  Jump walk 
                d[x] = d[u] + 1;
                vis[x] = true;
                q.add(x);
            }
        }
    }
}

5、 ... and   test

Green is the input , White is the output .