【华为OD-E卷-狼羊过河 100分（python、java、c++、js、c）】

python javacjsc_0">【华为OD-E卷-狼羊过河 100分（python、java、c++、js、c）】

题目

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

输入描述

第一行输入为M，N，X，分别代表羊的数量，狼的数量，小船的容量

输出描述

输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数（若无法满足条件则输出0）

用例

用例一：

输入：

5 3 3

输出：

用例二：

输入：

5 4 1

输出：

python_47">python解法

解题思路：
这道题目本质上是一个经典的“过河问题”，其中有两种角色（羊和狼）需要通过一只船过河。每次只能带走一些羊和一些狼，且船的容量有限制。目标是通过最少的步骤将所有的羊和狼都从起始位置带到对岸，并且需要遵循一些规则：

每次船上可以带的羊和狼的数量总和不能超过船的容量 boat。
每个岸上必须遵守羊的数量不能少于狼的数量，即如果岸上有狼且羊不足，狼会攻击羊。
思路步骤：
状态表示：每一个状态由五个变量表示：

s: 当前岸上的羊的数量。
w: 当前岸上的狼的数量。
ts: 已经成功到达对岸的羊的数量。
tw: 已经成功到达对岸的狼的数量。
steps: 当前状态下的步骤数。
目标：从起始状态 (m, n, 0, 0)（m 是羊的数量，n 是狼的数量）开始，通过合法的船次转移，最终达到 (0, 0, m, n)（所有羊和狼都到达对岸）所需的最小步骤数。

合法状态判断：每次我们尝试在船上带走 ns 只羊和 nw 只狼时，必须确保：

每次船的载重量不能超过容量 boat。
每个岸上不能有狼的数量多于羊，除非羊数量为零。
每次船的调度不能导致已经到达的羊和狼数量不合法（即不应违反任何规则）。
BFS算法：用宽度优先搜索（BFS）算法来计算最短步骤。BFS 适合用来解决最少步骤问题，因为它会遍历所有可能的状态，找到最短路径

python">from collections import dequedef find_min(sheep, wolf, boat):# 使用集合来记录访问过的状态，防止重复计算visited = set()# 队列初始化为起始状态（所有羊和狼在起始岸，已经过河的羊和狼为0，步数为0）queue = deque([(sheep, wolf, 0, 0, 0)])visited.add((sheep, wolf, 0, 0))  # 将初始状态加入visited集合# BFS搜索while queue:# 从队列中取出当前状态s, w, ts, tw, steps = queue.popleft()# 如果当前状态的羊和狼都到达对岸，返回步数if s == 0 and w == 0:return steps# 尝试所有合法的船次：带走ns只羊和nw只狼for ns in range(min(boat, s) + 1):  # ns为当前船上带走的羊的数量for nw in range(min(boat, w) + 1):  # nw为当前船上带走的狼的数量# 如果船上不带任何动物，则跳过if ns + nw == 0:continue# 如果船上带的羊和狼的数量超过船的容量，则跳过if ns + nw > boat:continue# 检查当前岸上羊和狼的情况，确保狼不会吃羊if s - ns < w - nw and s - ns > 0:continue# 检查已经到达的羊和狼的情况，确保狼不会吃羊if ts + ns < tw + nw and ts + ns > 0:continue# 检查是否超出边界（负数羊或狼）if s - ns < 0 or w - nw < 0:continue# 检查船上的动物是否合理，防止状态错误if s - ns > 0 and w - nw > 0 and s - ns < w - nw:continue# 计算新的状态（即更新羊和狼的数量，已经过河的数量）new_state = (s - ns, w - nw, ts + ns, tw + nw)# 如果新状态没有被访问过，则加入队列if new_state not in visited:visited.add(new_state)queue.append((s - ns, w - nw, ts + ns, tw + nw, steps + 1))return 0  # 如果无法到达目标状态，则返回0（不可能到达）if __name__ == "__main__":# 输入格式：羊的数量，狼的数量，船的容量m, n, x = map(int, input().split())# 调用函数并输出最小步数print(find_min(m, n, x))

java_129">java解法

解题思路
这是一个典型的“过河问题”，其中有两种动物（羊和狼）需要通过一只船过河。每次船上可以载一定数量的羊和狼，并且船的容量有限制。目标是通过最少的步骤，将所有的羊和狼从起始岸带到对岸，并且遵循以下规则：

每次船上带的羊和狼的数量总和不能超过船的容量 b。
每个岸上的羊和狼必须遵守狼不多于羊的规则，除非没有羊。
解题步骤：
状态表示：每个状态可以通过 5 个变量表示：

s: 当前岸上剩余的羊的数量。
w: 当前岸上剩余的狼的数量。
b: 船的最大载客数。
opp_s: 已经成功到达对岸的羊的数量。
opp_w: 已经成功到达对岸的狼的数量。
目标：通过递归方式探索所有可能的搬运方案，最少步骤将所有羊和狼都从起始岸搬到对岸。状态变化是递归进行的，每次通过递归检查合法的羊和狼的搬运数量。

合法性检查：

每次船上带的羊和狼的数量必须小于等于船的容量 b。
在当前岸和对岸，不能让狼的数量超过羊的数量，除非羊的数量为零。
防止重复访问相同的状态，避免无意义的计算。
递归策略：使用深度优先搜索（DFS）策略进行递归搜索，记录每种合法搬运方案的步数，最终返回最小的步数

java">import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取输入的羊的数量，狼的数量，船的容量int s = sc.nextInt();int w = sc.nextInt();int b = sc.nextInt();// 输出最小的步数System.out.println(minSteps(s, w, b));}// 计算最小步数的方法public static int minSteps(int s, int w, int b) {List<Integer> res = new ArrayList<>();  // 存储结果（所有合法的步数）// 从初始状态开始进行递归搜索search(s, w, b, 0, 0, 0, res);// 如果有合法的结果，返回最小的步数；否则返回0（无法完成任务）return res.isEmpty() ? 0 : Collections.min(res);}// 深度优先搜索（DFS）递归方法public static void search(int s, int w, int b, int opp_s, int opp_w, int cnt, List<Integer> res) {// 如果所有羊和狼都已到达对岸，记录步数if (s == 0 && w == 0) {res.add(cnt);  // 记录当前步数return;}// 如果当前岸上的羊和狼的总数不超过船的容量，直接转移并记录步数if (s + w <= b) {res.add(cnt + 1);return;}// 尝试不同数量的羊和狼一起过河for (int i = 0; i <= Math.min(b, s); i++) {  // i表示船上带走的羊的数量for (int j = 0; j <= Math.min(b, w); j++) {  // j表示船上带走的狼的数量// 如果船上不带任何羊或狼，则跳过if (i + j == 0 || i + j > b) continue;// 检查当前岸上，羊的数量不能小于狼的数量if (s - i <= w - j && s - i > 0) continue;// 检查对岸，已经过河的羊的数量不能小于狼的数量if (opp_s + i <= opp_w + j && opp_s + i > 0) continue;// 递归调用，将羊和狼从当前岸搬到对岸，步数加1search(s - i, w - j, b, opp_s + i, opp_w + j, cnt + 1, res);}}}
}

C++解法

解题思路

更新中

C解法

解题思路

更新中

JS解法

解题思路
这道题目涉及经典的“过河问题”，其中有两种动物（羊和狼）需要通过一只船过河。每次船上可以带一定数量的羊和狼，并且船的容量有限制。目标是通过最少的步数将所有羊和狼从起始岸带到对岸，并且遵循以下规则：

每次船上带的羊和狼的数量总和不能超过船的容量 boat。
每个岸上的羊和狼必须遵守狼不多于羊的规则，除非没有羊。
解题步骤：
状态表示：

s: 当前岸上的羊的数量。
w: 当前岸上的狼的数量。
os: 已经成功到达对岸的羊的数量。
ow: 已经成功到达对岸的狼的数量。
boat: 船的容量。
trips: 当前已执行的步数。
目标：通过递归方式探索所有可能的搬运方案，最少步骤将所有羊和狼从起始岸搬到对岸。每次递归都检查当前是否已经将所有羊和狼成功搬到对岸，如果是，则更新最小的步数。

合法性检查：确保在每个状态下，岸上的羊数量不会少于狼的数量，除非羊已经没有了。

递归策略：使用深度优先搜索（DFS）来模拟每次可能的羊和狼的搬运组合，确保每次递归前都验证当前状态是否合法。

javascript">const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });// 监听输入并开始计算最小步数
rl.on("line", (line) => {const [sheep, wolf, boat] = line.split(" ").map(Number);console.log(minTrips(sheep, wolf, boat));  // 输出最小的步数
});// 计算最小步数的函数
function minTrips(sheep, wolf, boat) {const res = { min: Infinity };  // 用于存储最小步数的结果，初始化为InfinityfindTrips(sheep, wolf, 0, 0, boat, 0, res);  // 调用递归函数进行计算return res.min === Infinity ? 0 : res.min;  // 如果未找到合法解，返回0；否则返回最小步数
}// 递归搜索所有可能的搬运方案
function findTrips(s, w, os, ow, boat, trips, res) {// 如果所有的羊和狼都已到达对岸，记录步数if (s === 0 && w === 0) {res.min = Math.min(res.min, trips);  // 更新最小步数return;}// 尝试所有合法的船次：带走i只羊和j只狼for (let i = 0; i <= Math.min(boat, s); i++) {  // i表示船上带走的羊的数量for (let j = 0; j <= Math.min(boat - i, w); j++) {  // j表示船上带走的狼的数量if (i + j === 0) continue;  // 如果船上不带任何动物，则跳过// 计算新状态const ns = s - i;  // 新的羊的数量const nw = w - j;  // 新的狼的数量const nos = os + i;  // 已到达对岸的羊的数量const now = ow + j;  // 已到达对岸的狼的数量// 如果新状态合法，递归进行下一步if (validState(ns, nw, nos, now)) {findTrips(ns, nw, nos, now, boat, trips + 1, res);}}}
}// 判断当前状态是否合法
function validState(s, w, os, ow) {// 1. 当前岸上羊的数量不能少于狼的数量，除非羊已经没有了// 2. 对岸上羊的数量不能少于狼的数量，除非羊已经没有了return !(s > 0 && s < w) && !(os > 0 && os < ow);
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏