【888题竞赛篇】第七题，2023ICPC沈阳-羊吃狼(Sheep Eat Wolves)

更多精彩内容

这里是带你游历编程世界的Dashcoding编程社，我是Dash/北航硕士/ICPC区域赛全国排名30+/给你呈现我们眼中的世界！

256题算法特训课，帮你斩获大厂60W年薪offer

原题

2023ICPC沈阳真题羊吃狼

B站动画详解

问题分析

这个问题涉及到通过BFS（广度优先搜索）和动态规划（DP）的方法来计算将所有羊安全运送回家的最少运输次数。我们需要处理的核心问题是，在任何时刻，狼的数量是否会对羊构成威胁。具体来说，当狼的数量严格大于羊的数量加上给定的阈值 $q$ 时，狼会吃掉羊。因此，在设计方案时，我们必须确保在任何时刻，农夫约翰都能够控制住狼和羊，以防止狼吃掉羊。

思路分析

算法的核心思想是使用状态表示和广度优先搜索来求解最少运输次数。我们定义状态 f[i][j][side]，其中 i 表示在当前岸边的羊的数量，j 表示在当前岸边的狼的数量，side 表示当前岸边是否是农夫约翰所在的岸边（0表示农夫在家那边，1表示农夫在河对岸）。使用BFS可以逐层探索所有可能的状态转移，从而找到最优解。

具体步骤如下：

1. 初始化：将所有状态 f[i][j][side] 初始化为无穷大（INF），表示初始状态不可达。设置初始状态为 f[x][y][0] = 0，表示在初始时，所有羊和狼在家那边，且农夫也在家那边。
2. 状态转移：从当前状态出发，尝试将不同数量的羊和狼运输到另一边。对每种运输方案进行状态转移，并更新最少步数。
3. 合法性检查：在进行状态转移时，检查是否符合安全条件，即狼的数量是否严格大于羊的数量加上阈值 q。
   最终结果：遍历所有可能的状态，找到将所有羊安全运送到对岸的最少步数。如果找不到合法的方案，则返回 -1。

算法实现

下面是使用广度优先搜索（BFS）结合动态规划（DP）解决该问题的实现。我们将定义状态 f[i][j][side] 表示在当前岸边有 i 只羊和 j 只狼，且农夫在与家不同侧的岸边时所需的最少步数（side 为0表示农夫在家那边，1表示农夫在对岸）。

代码详解

标准代码程序

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;int f[N][N][3], ans = INF;
struct node {int x, y, side;
};queue<node> Q;int main() {memset(f, INF, sizeof(f));int x, y, p, q;cin >> x >> y >> p >> q;// 初始化起始状态f[x][y][0] = 0;Q.push(node{x, y, 0});while (!Q.empty()) {node state = Q.front();Q.pop();int sheap = state.x;int wolf = state.y;int otherSheap = x - sheap;int otherWolf = y - wolf;int side = state.side;// 尝试将不同数量的羊和狼运输到另一边for (int i = 0; i <= min(sheap, p); i++) {for (int j = 0; j + i <= p && j <= wolf; j++) {int staySheap = sheap - i;int stayWolf = wolf - j;// 检查安全条件if (stayWolf > staySheap + q && staySheap) continue;// 更新状态if (f[otherSheap + i][otherWolf + j][side ^ 1] > f[sheap][wolf][side] + 1) {f[otherSheap + i][otherWolf + j][side ^ 1] = f[sheap][wolf][side] + 1;Q.push(node{otherSheap + i, otherWolf + j, side ^ 1});}}}}// 找到最少步数for (int i = 0; i <= y; i++) ans = min(ans, f[x][i][1]);if (ans == INF) cout << -1;else cout << ans;return 0;
}

Java代码

import java.util.*;public class Main {static final int N = 105;static final int INF = Integer.MAX_VALUE;static int[][][] f = new int[N][N][3];static int ans = INF;static class Node {int x, y, side;Node(int x, int y, int side) {this.x = x;this.y = y;this.side = side;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);for (int[][] arr2D : f) {for (int[] arr1D : arr2D) {Arrays.fill(arr1D, INF);}}int x = sc.nextInt();int y = sc.nextInt();int p = sc.nextInt();int q = sc.nextInt();f[x][y][0] = 0;Queue<Node> Q = new LinkedList<>();Q.add(new Node(x, y, 0));while (!Q.isEmpty()) {Node state = Q.poll();int sheap = state.x;int wolf = state.y;int otherSheap = x - sheap;int otherWolf = y - wolf;int side = state.side;for (int i = 0; i <= Math.min(sheap, p); i++) {for (int j = 0; j + i <= p && j <= wolf; j++) {int staySheap = sheap - i;int stayWolf = wolf - j;if (stayWolf > staySheap + q && staySheap > 0) continue;if (f[otherSheap + i][otherWolf + j][side ^ 1] > f[sheap][wolf][side] + 1) {f[otherSheap + i][otherWolf + j][side ^ 1] = f[sheap][wolf][side] + 1;Q.add(new Node(otherSheap + i, otherWolf + j, side ^ 1));}}}}for (int i = 0; i <= y; i++) {ans = Math.min(ans, f[x][i][1]);}System.out.println(ans == INF ? -1 : ans);}
}

Python代码

from collections import dequedef main():INF = float('inf')N = 105f = [[[INF] * 3 for _ in range(N)] for _ in range(N)]ans = INFx, y, p, q = map(int, input().split())f[x][y][0] = 0Q = deque([(x, y, 0)])while Q:sheap, wolf, side = Q.popleft()otherSheap = x - sheapotherWolf = y - wolffor i in range(min(sheap, p) + 1):for j in range(min(p - i, wolf) + 1):staySheap = sheap - istayWolf = wolf - jif stayWolf > staySheap + q and staySheap > 0:continueif f[otherSheap + i][otherWolf + j][side ^ 1] > f[sheap][wolf][side] + 1:f[otherSheap + i][otherWolf + j][side ^ 1] = f[sheap][wolf][side] + 1Q.append((otherSheap + i, otherWolf + j, side ^ 1))for i in range(y + 1):ans = min(ans, f[x][i][1])print(-1 if ans == INF else ans)if __name__ == "__main__":main()

Javascript代码

function minTransport(x, y, p, q) {const N = 105;const INF = Infinity;let f = Array.from({ length: N }, () => Array.from({ length: N }, () => [INF, INF, INF]));let ans = INF;// 初始状态f[x][y][0] = 0;let queue = [{ x, y, side: 0 }];while (queue.length > 0) {let { x: sheap, y: wolf, side } = queue.shift();let otherSheap = x - sheap;let otherWolf = y - wolf;for (let i = 0; i <= Math.min(sheap, p); i++) {for (let j = 0; j + i <= p && j <= wolf; j++) {let staySheap = sheap - i;let stayWolf = wolf - j;if (stayWolf > staySheap + q && staySheap > 0) continue;if (f[otherSheap + i][otherWolf + j][side ^ 1] > f[sheap][wolf][side] + 1) {f[otherSheap + i][otherWolf + j][side ^ 1] = f[sheap][wolf][side] + 1;queue.push({ x: otherSheap + i, y: otherWolf + j, side: side ^ 1 });}}}}for (let i = 0; i <= y; i++) {ans = Math.min(ans, f[x][i][1]);}return ans === INF ? -1 : ans;
}

复杂度分析

时间复杂度

在这个问题中，我们使用了广度优先搜索（BFS）来解决问题。下面是时间复杂度的详细分析：

1. 状态空间：

   • 状态表示为 $(\text{sheep},\text{wolf},\text{side})$，其中 $\text{sheep}$ 的取值范围是 $0$ 到 $x$，$\text{wolf}$ 的取值范围是 $0$ 到 $y$，$\text{side}$ 取值为 $0$ 或 $1$。
   • 因此，状态空间的总大小为 $(x+1)\times (y+1)\times 2$，即 $O(x\times y)$。

2. 状态转移：

   • 对于每个状态 $(\text{sheep},\text{wolf},\text{side})$，我们尝试将不同数量的羊和狼运输到对岸。最坏情况下，我们需要检查 $p$ 个位置的羊和狼组合。
   • 因此，每个状态的处理时间为 $O(p^2)$。

3. 总体时间复杂度：

   • 状态空间的大小是 $O(x\times y)$。
   • 每个状态的处理时间是 $O(p^2)$。
   • 因此，总体时间复杂度是 $O(x\times y\times p^2)$。

空间复杂度

1. 状态存储：

• 使用了一个三维数组 $f$ 来存储状态信息，其大小为 $(x+1)\times (y+1)\times 2$，即 $O(x\times y)$。

2. 队列存储：

   • BFS 使用了一个队列来存储状态。队列中最多可能有 $O(x\times y)$ 个状态，每个状态占用常量空间。

3. 总体空间复杂度：

   • 状态存储和队列存储的空间复杂度是 $O(x\times y)$。

总结

这个算法通过广度优先搜索（BFS）和动态规划（DP）的结合，能够有效地解决将羊安全运输到对岸的问题。时间复杂度为 $O(x\times y\times p^2)$，空间复杂度为 $O(x\times y)$，使得它在给定的输入范围内（$x,y\le 100$）能够在合理的时间内运行。算法确保了所有可能的运输方案都被探索，并找到最优解。如果无法安全运输所有羊，则返回 $-1$。