【华为OD-E卷-狼羊过河 100分（python、java、c++、js、c）】
题目
羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。
要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。
只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。
输入描述
- 第一行输入为M，N，X， 分别代表羊的数量，狼的数量，小船的容量
输出描述
- 输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数（若无法满足条件则输出0）
用例
用例一：
输入：
5 3 3
- 1
输出：
3
- 1
用例二：
输入：
5 4 1
- 1
输出：
0
- 1
python解法
- 解题思路：
- 这道题目本质上是一个经典的“过河问题”，其中有两种角色（羊和狼）需要通过一只船过河。每次只能带走一些羊和一些狼，且船的容量有限制。目标是通过最少的步骤将所有的羊和狼都从起始位置带到对岸，并且需要遵循一些规则：
每次船上可以带的羊和狼的数量总和不能超过船的容量 boat。
每个岸上必须遵守羊的数量不能少于狼的数量，即如果岸上有狼且羊不足，狼会攻击羊。
思路步骤：
状态表示：每一个状态由五个变量表示：
s: 当前岸上的羊的数量。
w: 当前岸上的狼的数量。
ts: 已经成功到达对岸的羊的数量。
tw: 已经成功到达对岸的狼的数量。
steps: 当前状态下的步骤数。
目标：从起始状态 (m, n, 0, 0)（m 是羊的数量，n 是狼的数量）开始，通过合法的船次转移，最终达到 (0, 0, m, n)（所有羊和狼都到达对岸）所需的最小步骤数。
合法状态判断：每次我们尝试在船上带走 ns 只羊和 nw 只狼时，必须确保：
每次船的载重量不能超过容量 boat。
每个岸上不能有狼的数量多于羊，除非羊数量为零。
每次船的调度不能导致已经到达的羊和狼数量不合法（即不应违反任何规则）。
BFS算法：用宽度优先搜索（BFS）算法来计算最短步骤。BFS 适合用来解决最少步骤问题，因为它会遍历所有可能的状态，找到最短路径
from collections import deque
def 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
java解法
- 解题思路
- 这是一个典型的“过河问题”，其中有两种动物（羊和狼）需要通过一只船过河。每次船上可以载一定数量的羊和狼，并且船的容量有限制。目标是通过最少的步骤，将所有的羊和狼从起始岸带到对岸，并且遵循以下规则：
每次船上带的羊和狼的数量总和不能超过船的容量 b。
每个岸上的羊和狼必须遵守狼不多于羊的规则，除非没有羊。
解题步骤：
状态表示：每个状态可以通过 5 个变量表示：
s: 当前岸上剩余的羊的数量。
w: 当前岸上剩余的狼的数量。
b: 船的最大载客数。
opp_s: 已经成功到达对岸的羊的数量。
opp_w: 已经成功到达对岸的狼的数量。
目标：通过递归方式探索所有可能的搬运方案，最少步骤将所有羊和狼都从起始岸搬到对岸。状态变化是递归进行的，每次通过递归检查合法的羊和狼的搬运数量。
合法性检查：
每次船上带的羊和狼的数量必须小于等于船的容量 b。
在当前岸和对岸，不能让狼的数量超过羊的数量，除非羊的数量为零。
防止重复访问相同的状态，避免无意义的计算。
递归策略：使用深度优先搜索（DFS）策略进行递归搜索，记录每种合法搬运方案的步数，最终返回最小的步数
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;
// 递归调用，将羊和狼从当前岸搬到对岸，步数加1
search(s - i, w - j, b, opp_s + i, opp_w + j, cnt + 1, res);
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
-
解题思路
-
这道题目涉及经典的“过河问题”，其中有两种动物（羊和狼）需要通过一只船过河。每次船上可以带一定数量的羊和狼，并且船的容量有限制。目标是通过最少的步数将所有羊和狼从起始岸带到对岸，并且遵循以下规则：
每次船上带的羊和狼的数量总和不能超过船的容量 boat。
每个岸上的羊和狼必须遵守狼不多于羊的规则，除非没有羊。
解题步骤：
状态表示：
s: 当前岸上的羊的数量。
w: 当前岸上的狼的数量。
os: 已经成功到达对岸的羊的数量。
ow: 已经成功到达对岸的狼的数量。
boat: 船的容量。
trips: 当前已执行的步数。
目标：通过递归方式探索所有可能的搬运方案，最少步骤将所有羊和狼从起始岸搬到对岸。每次递归都检查当前是否已经将所有羊和狼成功搬到对岸，如果是，则更新最小的步数。
合法性检查：确保在每个状态下，岸上的羊数量不会少于狼的数量，除非羊已经没有了。
递归策略：使用深度优先搜索（DFS）来模拟每次可能的羊和狼的搬运组合，确保每次递归前都验证当前状态是否合法。
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 }; // 用于存储最小步数的结果，初始化为Infinity
findTrips(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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：