一、题目描述
羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。
要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。
只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。
二、输入输出描述
输入描述
- 第一行：三个整数M，N，X， 分别代表羊的数量，狼的数量，小船的容量。
输出描述
- 一个整数，表示安全运输所有羊和狼到对岸的最小次数；若无法完成则输出 0。
三、示例
| 输入 |
5 3 3 |
| 输出 | 3 |
| 说明 |
第一次运2只狼 第二次运3只羊 第三次运2只羊和1只狼 |
| 输入 | 5 4 1 |
| 输出 | 0 |
| 说明 | 如果找不到不损失羊的运送方案，输出0 |
四、解题思路
1. 核心思想
采用DFS 枚举 + 剪枝优化的策略，遍历所有合法的 “单次运送组合”，通过递归探索完整的运送路径，记录所有能将羊狼全运完的次数，最终取最小值。核心是 “枚举所有可能，剪枝排除不安全 / 无意义的路径，保证只探索有效解”。
2. 问题本质分析
- 表层问题：找到羊狼过河的最少运送次数；
- 深层问题：
3. 核心逻辑
- 状态枚举：双重循环枚举单次运送的羊、狼数量组合；
- 安全校验：校验本岸、对岸运送后的状态是否安全；
- 剪枝优化：提前排除空运、超载、不安全、后续无法挽救的组合；
- 递归探索：合法组合则递归更新状态，继续探索下一次运送；
- 结果收集：到达终止状态时记录次数，最终返回最小值。
4. 步骤拆解
初始状态初始化
- 输入本岸羊数sheep、狼数wolf、船负载boat；
- 初始化结果集合ans，启动 DFS（初始对岸 0 羊 0 狼，次数 0）。
DFS 终止条件判断
- 若本岸羊狼都为 0：将当前次数加入ans，返回；
- 若剩余羊狼总数≤船负载：将次数 + 1 加入ans，返回（一次运完）。
枚举单次运送组合
- 外层循环：枚举船上羊数i（0 到min(boat, sheep)）；
- 内层循环：枚举船上狼数j（0 到min(boat, wolf)）。
剪枝过滤无效组合
- 排除空运（i+j=0）、超载（i+j>boat）；
- 排除本岸运送后不安全的组合（剩余羊 > 0 且羊≤狼）；
- 排除对岸运送后不安全的组合（新增羊 > 0 且羊≤狼）；
- 排除对岸无羊但狼≥船负载的组合（后续无法挽救）。
递归探索下一次运送
- 更新本岸：羊数sheep-i，狼数wolf-j；
- 更新对岸：羊数oppo_sheep+i，狼数oppo_wolf+j；
- 次数 + 1，继续递归。
结果处理
- 所有递归结束后，若ans非空，返回最小值（最少次数）；
- 若无合法解，返回 0。
五、代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int x = sc.nextInt();
System.out.println(getResult(m, n, x));
}
/**
* @param sheep 本岸羊数量
* @param wolf 本岸狼数量
* @param boat 船负载
* @return 最少运送次数
*/
public static int getResult(int sheep, int wolf, int boat) {
ArrayList<Integer> ans = new ArrayList<>();
dfs(sheep, wolf, boat, 0, 0, 0, ans);
if (ans.size() > 0) {
return Collections.min(ans);
} else {
return 0;
}
}
public static void dfs(
int sheep,
int wolf,
int boat,
int oppo_sheep,
int oppo_wolf,
int count,
ArrayList<Integer> ans) {
if (sheep == 0 && wolf == 0) {
ans.add(count);
return;
}
if (sheep + wolf <= boat) {
ans.add(count + 1);
return;
}
// i 代表船上羊数量，最多Math.min(boat, sheep)
for (int i = 0; i <= Math.min(boat, sheep); i++) {
// j 代表船上狼数量，最多Math.min(boat, wolf)
for (int j = 0; j <= Math.min(boat, wolf); j++) {
// 空运
if (i + j == 0) continue;
// 超载
if (i + j > boat) break;
// 本岸羊 <= 本岸狼，说明狼运少了
if (sheep – i <= wolf – j && sheep – i != 0) continue;
// 对岸羊 <= 对岸狼，说明狼运多了
if (oppo_sheep + i <= oppo_wolf + j && oppo_sheep + i != 0) break;
// 对岸没羊，但是对岸狼已经超过船载量，即下次即使整船都运羊，也无法保证对岸羊 > 对岸狼
if (oppo_sheep + i == 0 && oppo_wolf + j >= boat) break;
dfs(sheep – i, wolf – j, boat, oppo_sheep + i, oppo_wolf + j, count + 1, ans);
}
}
}
}
