华为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）代码随想录回溯专题