Depth first search to realize the problem of catching 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.Scanner;

public class POJ3278 {
    static private int n;
    static private int k;

    /**
     *  Function description ： Depth-first algorithm 
     *
     * @param t  Location of cattle 
     * @return  Required deployment 
     * @author cakin
     * @date 2022/6/28
     * @description:
     */
    static int dfs(int t) {
        if (t <= n) //  People step backwards 
            return n - t;
        if (t % 2 != 0) //  People are  t+1  Location , Take another step to the cow's position ,  People are  t-1  Location , Take another step to the cow's position 
            return Math.min(dfs(t + 1) + 1, dfs(t - 1) + 1);
        else //  People are  t/2  The location of , Take another step to the cow's position , People directly from  n  Go to the  t Steps 
            return Math.min(dfs(t / 2) + 1, t - n);
    }

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


        int ans = 0;
        if (n == 0) { //  Judgment of special circumstances , Very important 
            n = 1;
            ans = 1;
        }
        ans += dfs(k);
        System.out.println(ans);
    }
}

5、 ... and   test result

Green is the input , White is the output