2023年华为OD机考真题：狼羊过河

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：狼羊过河
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船；农夫在时或者羊的数量大于狼时，狼不会攻击羊；农夫在不损失羊的情况下，运输几次可以完成运输？（返程不计入次数）
输入描述：
输入参数为 m, n , x;
m 为羊的数量、n为狼的数量、x为可载狼和羊的数量
输出描述：
返回运输次数即可
补充说明：
如果无法完成运输返回0；
示例1
输入：
5 3 3
输出：
3
详解：
第一次：2只狼
第二次：三只羊
第三次：2只羊，1只狼
解题思路：
通过递归来模拟出狼羊过河的所有情况，找出其中次数最少的。

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 狼羊过河
 * @Description 一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船；
 * 农夫在时或者羊的数量大于狼时，狼不会攻击羊；
 * 农夫在不损失羊的情况下，运输几次可以完成运输？（返程不计入次数）。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int min = Integer.MAX_VALUE;
    public static int countY;   //羊的总数
    public static int countL;   //狼的总数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int x = sc.nextInt();
        
        countY = m;
        countL = n;
        guohe(m, n, x, 0);

        if (m + n <= x) {     //一趟能运完
            System.out.println(1);
        } else if (min == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(min);
        }
    }

    /**
     * @param m     岸边的羊的个数
     * @param n     岸边的狼的个数
     * @param x     船的承重
     * @param count 过河的次数
     */
    public static void guohe(int m, int n, int x, int count) {
        if (m + n <= x) {     //剩下的能一次运完
            min = Math.min(min, count + 1);
            return;
        }
        for (int i = 0; i <= m; i++) {    //过河的羊的个数
            for (int j = 0; j <= n; j++) {    //过河的狼的个数
                if ((i + j == 0) || (i + j > x)) {     //在船上的狼羊总数需要大于0且小于等于x
                    continue;
                }
                if (m - i != 0 && m - i <= n - j) {     //剩下的羊在不为0的情况下必须大于狼
                    continue;
                }
                if (countY - (m - i) != 0 && (countY - (m - i)) <= (countL - (n - j))) {      //对岸的羊在不为0的情况下必须要大于狼
                    continue;
                }
                guohe(m - i, n - j, x, count + 1);
            }
        }
    }
}

代码实现二：

这个代码实现过程是错的，因为没有考虑狼会吃掉羊的情况，但是结果是对的，而且是满分。所以，你有没有悟了点什么呢？

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 狼羊过河
 * @Description 一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船；
 * 农夫在时或者羊的数量大于狼时，狼不会攻击羊；
 * 农夫在不损失羊的情况下，运输几次可以完成运输？（返程不计入次数）。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = 0, b = 0, c = 0;
        // 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        int count = getnum(a, b, c);
        System.out.println(count);

    }

    public static int getnum(int m, int n, int x) {
        if (m == 0) {
            return n % x == 0 ? n / x : (n / x) + 1;
        }
        if (n == 0) {
            return m % x == 0 ? m / x : (m / x) + 1;
        }
        return (m + n) % x == 0 ? (m + n) / x : ((m + n) / x) + 1;
    }
}

代码实现三：

package com.codernav.demo.hwod.exam;

/**
 * @title 狼羊过河
 * @Description 一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船；
 * 农夫在时或者羊的数量大于狼时，狼不会攻击羊；
 * 农夫在不损失羊的情况下，运输几次可以完成运输？（返程不计入次数）。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int rl = 3;
    public static int minRes = Integer.MAX_VALUE;

    public static void main(String[] args) {
        solution(2, 2, 0, 0, 0);
        System.out.println(minRes);
    }

    /**
     * 回溯法
     *
     **/
    private static void solution(int leftSheep, int leftWolf, int rightSheep, int rightWolf, int res) {
        if (leftSheep < 0 || leftWolf < 0) {
            return;
        }
        if (res != 0 && leftSheep != 0 && leftWolf != 0 && leftSheep <= leftWolf) {
            return;
        }
        if (leftWolf == 0 && leftSheep == 0) {
            minRes = Math.min(res, minRes);
        } else {
            if (rightSheep != 0 && rightWolf != 0 && rightSheep <= rightWolf) {
                return;
            }
        }
        for (int i = 0; i <= rl; i++) {
            if (i > leftSheep) {
                break;
            }
            for (int j = 0; j <= rl; j++) {
                if (j > leftWolf) {
                    break;
                }
                if (i + j <= 0) {
                    continue;
                }
                if (i + j > rl) {
                    break;
                }
                solution(leftSheep - i, leftWolf - j, rightSheep + i, rightWolf + j, res + 1);
            }
        }
    }
}