一 原问题链接

3278 -- Catch That Cow

http://poj.org/problem?id=3278

二 输入和输出

1 输入

两个数，第1个数代表农夫的位置，第2个数代表牛的位置。

2 输出

农夫抓牛的最小步数

三 输入和输出样例

1 输入样例

5 17

2 输出样例

4

四 代码

package graph.poj3278;

import java.util.Scanner;

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

    /**
     * 功能描述：深度优先算法
     *
     * @param t 牛的位置
     * @return 需要的部署
     * @author cakin
     * @date 2022/6/28
     * @description:
     */
    static int dfs(int t) {
        if (t <= n) // 人后退步数
            return n - t;
        if (t % 2 != 0) // 人在 t+1 位置，再走一步到牛的位置, 人在 t-1 位置，再走一步到牛的位置
            return Math.min(dfs(t + 1) + 1, dfs(t - 1) + 1);
        else // 人在 t/2 的位置，再走一步到牛的位置，人直接从 n 走到 t的步数
            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) { // 特殊情况判断，很重要
            n = 1;
            ans = 1;
        }
        ans += dfs(k);
        System.out.println(ans);
    }
}

五 测试结果

绿色为输入，白色为输出