华为OD机试真题【羊狼农夫过河】

这篇具有很好参考价值的文章主要介绍了华为OD机试真题【羊狼农夫过河】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、题目描述

【羊、狼、农夫过河】
羊、狼、农夫都在岸边,当羊的数量小于狼的数量时,狼会攻击羊,农夫则会损失羊。农夫有一艘容量固定的船,能够承载固定数量的动物。要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数,回程时农夫不会运送羊和狼。
备注:农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。农夫自身不占用船的容量。

【输入描述】
第一行输入为M,N,X, 分别代表羊的数量,狼的数量,小船的容量。

【输出描述】
输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数(若无法满足条件则输出0)。

【示例1】
输入: 5 3 3
输出: 3
说明:第一次运2只狼第二次运3只羊第三次运2只羊和1只狼

【示例2】
输入: 5 4 1
输出: 0
说明:如果找不到不损失羊的运送方案,输出0

2、解题思路

初始化一个变量minTimes为(羊数量+狼数量) *小船容量;
定义一个回溯DFS方法, 用于模拟过河的过程,每次递归计算 当前状态下的最小运输次数;
在DFS函数中,遍历尝试所有可能的运输组合,保证组合中羊的数量大于等于狼的数量,以防止羊被狼吃掉;
在递归过程中,如果发现某种组合能够使得所有羊和狼都运到对岸,且所需次数小于当前记录的最小次数,则更新最小次数;
后输出最小运输次数。如果没有找到满足条件的运输方案,输出0。

3、参考代码

import java.util.Scanner;

public class 羊狼农夫过河 {
    public static int minTimes = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();  // 羊数量
            int n = in.nextInt();  // 狼数量
            int x = in.nextInt();  // 小船数量
            minTimes = 0;
            dfs(m, n, x, 0, 0, 0);

            if (minTimes == Integer.MAX_VALUE) {
                System.out.println(0);
            } else {
                System.out.println(minTimes);
            }
        }
    }

    public static int dfs(int m, int n, int x, int m1, int n1, int times) {
       // 如果小船容量足够运输所有羊和狼,则只需要一次即可
        if (x >= m + n) {
            if (times + 1 < minTimes) {
                minTimes = times + 1;
            }
            return times + 1;
        }

        // 遍历所有的运输组合,保证组合中羊的数量大于狼的数量
        for (int i = 0; i <= m && i <= x; i++) {
            for (int j = 0; j <= n && i + j <= x; j++) {
                if (i + j == 0) {
                    continue;
                }

                // 船离岸后,原来这岸,要么没有羊,要么羊比狼多
                if ((m - i == 0 || m - i > n - j) && (m1 + i == 0 || m1 + i > n + j)) {
                    int result = dfs(m, n, x, m - i, n - j, times + 1);
                    if (result < minTimes && result != 0) {
                        minTimes = result;
                    }
                }
            }
        }
        return 0;
    }
}

4、相似题目

(1)代码随想录回溯专题文章来源地址https://www.toymoban.com/news/detail-682689.html

到了这里,关于华为OD机试真题【羊狼农夫过河】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(45)
  • 【华为OD机试真题 JAVA】算法中的常用知识点

            IndexOf():返回指定字符在字符串中第一次出现处的索引,如果此字符串中没有这                             样的字符,则返回 -1。         charAt(i):返回指定索引 i 处的字符。索引范围为从 0 到 length() - 1。         equals(s):将字符串与指定

    2024年02月10日
    浏览(45)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(52)
  • 【华为OD机试真题 C++】1118 - 最大利润 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Python语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 商人经营一家店铺, 有number种商品,由于仓库限

    2024年02月04日
    浏览(56)
  • 【华为OD机试真题 C++语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用C++语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1

    2024年02月16日
    浏览(58)
  • 【华为OD机试真题 Java语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Java语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1  

    2024年02月14日
    浏览(50)
  • 【华为OD机试真题 C++】1109 - 优雅子数组 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Python语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述

    2024年02月06日
    浏览(49)
  • 【华为OD机试真题 Python语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: 鲨鱼狼臧   🍂专栏介绍: 2023华为OD机试真题,使用Python进行解答,专栏每篇文章都包括真题,思路参考,代码分析,订阅有问题后续可与博主解答问题 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1   其中值为1的成员具备扩散性,每经过

    2024年02月15日
    浏览(51)
  • 260.【华为OD机试真题】信道分配(贪心算法-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月20日
    浏览(53)
  • 【华为OD机试真题 C++】1060 - 翻牌求最大分 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用C语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 给出n个牌数,在-10到100之间,求最大得分。  

    2023年04月22日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包