你想要“华为OD机考2025B卷 – 士兵过河”这个题目的多语言版本解题思路和代码示例吗？我可以帮你准备Java、Python、JavaScript、C++和C的完整代码和解析。先给你题目描述和通用解法思路，然后逐语言实现代码，怎么样？如果你有题目详细描述或者具体要求，告诉我更好帮你定制。
士兵过河 – 题目描述（假设示例）
题目通常是经典的“士兵过河”问题，比如：
- 有一条河，有一群士兵要过河，每次船只能载一定人数。
- 有一些限制条件，如不同类型士兵不能单独留在岸上，或士兵和敌人比例限制等。
- 求最少过河次数或判断是否能过河。
如果你有具体题目文本，发给我。
通用解题思路
- 状态表示
通过一个数据结构表示当前两岸士兵的状态和船的位置。 - 状态转移
模拟士兵过河动作，符合限制条件则转移。 - 搜索策略
BFS或DFS遍历状态空间，找最优解。 - 剪枝
剪去不合法或重复状态，提升效率。
Java示例代码（模板）
import java.util.*;
public class SoldierCrossRiver {
static class State {
int leftA, leftB; // 左岸士兵A、B数量
int rightA, rightB;
boolean boatOnLeft;
State(int la, int lb, int ra, int rb, boolean boat) {
leftA = la; leftB = lb; rightA = ra; rightB = rb; boatOnLeft = boat;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State s = (State) o;
return leftA == s.leftA && leftB == s.leftB && rightA == s.rightA && rightB == s.rightB && boatOnLeft == s.boatOnLeft;
}
@Override
public int hashCode() {
return Objects.hash(leftA, leftB, rightA, rightB, boatOnLeft);
}
}
// 判断状态是否合法
static boolean isValid(State s) {
if (s.leftA < 0 || s.leftB < 0 || s.rightA < 0 || s.rightB < 0) return false;
if (s.leftA > 0 && s.leftA < s.leftB) return false;
if (s.rightA > 0 && s.rightA < s.rightB) return false;
return true;
}
public static int minCrossing(int totalA, int totalB, int boatCapacity) {
State start = new State(totalA, totalB, 0, 0, true);
State end = new State(0, 0, totalA, totalB, false);
Queue<State> queue = new LinkedList<>();
Map<State, Integer> dist = new HashMap<>();
queue.offer(start);
dist.put(start, 0);
while (!queue.isEmpty()) {
State curr = queue.poll();
int step = dist.get(curr);
if (curr.equals(end)) return step;
// 枚举船上可能载的士兵数目组合
for (int a = 0; a <= boatCapacity; a++) {
for (int b = 0; b <= boatCapacity - a; b++) {
if (a + b == 0) continue;
State next = null;
if (curr.boatOnLeft) {
next = new State(
curr.leftA - a, curr.leftB - b,
curr.rightA + a, curr.rightB + b,
false
);
} else {
next = new State(
curr.leftA + a, curr.leftB + b,
curr.rightA - a, curr.rightB - b,
true
);
}
if (isValid(next) && !dist.containsKey(next)) {
dist.put(next, step + 1);
queue.offer(next);
}
}
}
}
return -1; // 无解
}
public static void main(String[] args) {
int A = 3; // 士兵A数量
int B = 3; // 士兵B数量
int boatCap = 2; // 船容量
int res = minCrossing(A, B, boatCap);
System.out.println(res == -1 ? "无法过河" : "最少过河次数：" + res);
}
}
Python示例代码
from collections import deque
class State:
def __init__(self, leftA, leftB, rightA, rightB, boatOnLeft):
self.leftA = leftA
self.leftB = leftB
self.rightA = rightA
self.rightB = rightB
self.boatOnLeft = boatOnLeft
def is_valid(self):
if any(x < 0 for x in [self.leftA, self.leftB, self.rightA, self.rightB]):
return False
if self.leftA > 0 and self.leftA < self.leftB:
return False
if self.rightA > 0 and self.rightA < self.rightB:
return False
return True
def __eq__(self, other):
return (self.leftA, self.leftB, self.rightA, self.rightB, self.boatOnLeft) == \
(other.leftA, other.leftB, other.rightA, other.rightB, other.boatOnLeft)
def __hash__(self):
return hash((self.leftA, self.leftB, self.rightA, self.rightB, self.boatOnLeft))
def min_crossing(totalA, totalB, boat_capacity):
start = State(totalA, totalB, 0, 0, True)
end = State(0, 0, totalA, totalB, False)
queue = deque([start])
visited = {start: 0}
while queue:
curr = queue.popleft()
step = visited[curr]
if curr == end:
return step
for a in range(boat_capacity + 1):
for b in range(boat_capacity + 1 - a):
if a + b == 0:
continue
if curr.boatOnLeft:
next_state = State(
curr.leftA - a, curr.leftB - b,
curr.rightA + a, curr.rightB + b,
False
)
else:
next_state = State(
curr.leftA + a, curr.leftB + b,
curr.rightA - a, curr.rightB - b,
True
)
if next_state.is_valid() and next_state not in visited:
visited[next_state] = step + 1
queue.append(next_state)
return -1
if __name__ == "__main__":
A = 3
B = 3
boat_capacity = 2
result = min_crossing(A, B, boat_capacity)
if result == -1:
print("无法过河")
else:
print(f"最少过河次数：{result}")
JavaScript示例（Node.js环境）
class State {
constructor(leftA, leftB, rightA, rightB, boatOnLeft) {
this.leftA = leftA;
this.leftB = leftB;
this.rightA = rightA;
this.rightB = rightB;
this.boatOnLeft = boatOnLeft;
}
isValid() {
if ([this.leftA, this.leftB, this.rightA, this.rightB].some(x => x < 0)) return false;
if (this.leftA > 0 && this.leftA < this.leftB) return false;
if (this.rightA > 0 && this.rightA < this.rightB) return false;
return true;
}
toString() {
return `${this.leftA},${this.leftB},${this.rightA},${this.rightB},${this.boatOnLeft}`;
}
}
function minCrossing(totalA, totalB, boatCapacity) {
let start = new State(totalA, totalB, 0, 0, true);
let endStr = `0,0,${totalA},${totalB},false`;
let queue = [start];
let visited = new Map();
visited.set(start.toString(), 0);
while (queue.length) {
let curr = queue.shift();
let step = visited.get(curr.toString());
if (curr.toString() === endStr) return step;
for (let a = 0; a <= boatCapacity; a++) {
for (let b = 0; b <= boatCapacity - a; b++) {
if (a + b === 0) continue;
let next;
if (curr.boatOnLeft) {
next = new State(
curr.leftA - a, curr.leftB - b,
curr.rightA + a, curr.rightB + b,
false
);
} else {
next = new State(
curr.leftA + a, curr.leftB + b,
curr.rightA - a, curr.rightB - b,
true
);
}
if (next.isValid() && !visited.has(next.toString())) {
visited.set(next.toString(), step + 1);
queue.push(next);
}
}
}
}
return -1;
}
// 示例调用
const A = 3;
const B = 3;
const boatCapacity = 2;
const result = minCrossing(A, B, boatCapacity);
if (result === -1) {
console.log("无法过河");
} else {
console.log(`最少过河次数：${result}`);
}
C++示例代码
#include <iostream>
#include <queue>
#include <unordered_set>
#include <tuple>
using namespace std;
struct State {
int leftA, leftB, rightA, rightB;
bool boatOnLeft;
State(int la, int lb, int ra, int rb, bool boat)
: leftA(la), leftB(lb), rightA(ra), rightB(rb), boatOnLeft(boat) {}
bool isValid() const {
if (leftA < 0 || leftB < 0 || rightA < 0 || rightB < 0) return false;
if (leftA > 0 && leftA < leftB) return false;
if (rightA > 0 && rightA < rightB) return false;
return true;
}
bool operator==(const State& other) const {
return tie(leftA, leftB, rightA, rightB, boatOnLeft) ==
tie(other.leftA, other.leftB, other.rightA, other.rightB, other.boatOnLeft);
}
};
struct StateHash {
size_t operator()(const State& s) const {
return hash<int>()(s.leftA) ^ hash<int>()(s.leftB) ^ hash<int>()(s.rightA) ^ hash<int>()(s.rightB) ^ hash<bool>()(s.boatOnLeft);
}
};
int minCrossing(int totalA, int totalB, int boatCapacity) {
State start(totalA, totalB, 0, 0, true);
State end(0, 0, totalA, totalB, false);
queue<State> q;
unordered_set<State, StateHash> visited;
q.push(start);
visited.insert(start);
int steps = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
State curr = q.front(); q.pop();
if (curr == end) return steps;
for (int a = 0; a <= boatCapacity; a++) {
for (int b = 0; b <= boatCapacity - a; b++) {
if (a + b == 0) continue;
State next = curr;
if (curr.boatOnLeft) {
next.leftA -= a; next.leftB -= b;
next.rightA += a; next.rightB += b;
next.boatOnLeft = false;
} else {
next.leftA += a; next.leftB += b;
next.rightA -= a; next.rightB -= b;
next.boatOnLeft = true;
}
if (next.isValid() && visited.find(next) == visited.end()) {
visited.insert(next);
q.push(next);
}
}
}
}
steps++;
}
return -1;
}
int main() {
int A = 3, B = 3, boatCapacity = 2;
int res = minCrossing(A, B, boatCapacity);
if (res == -1) cout << "无法过河\n";
else cout << "最少过河次数：" << res << "\n";
return 0;
}
C语言示例提示
- 由于C语言没有内置队列和哈希表，需要自己实现队列和状态存储结构，或用二维数组模拟状态。
- 也可以用数组+标记法实现BFS。
- 如果需要，我可以帮你写C语言版本的伪代码或完整代码。
发表回复