题解：

一、问题转化 我们有一个 $2$ 行 $n$ 列的网格。每个格子可能是空地（'.'）、羊（'S'）或狼（'W'）。羊有且仅有一只，且与羊相邻的格子中没有狼。我们可以支付 $h$ 金币消灭一只狼（将 'W' 变为 '.'），或支付 $b$ 金币在一个空格子上挖壕沟（该格子狼无法通过）。目标是使所有狼都无法到达羊所在格子，求最小总花费。

这等价于：在一个点带权的网格图中，删除一些点（消灭狼或挖壕沟），使得所有狼所在的点与羊所在的点不连通。删除一个狼点花费 $h$，删除一个空点花费 $b$，羊点不可删除。求满足条件的最小删除总代价。这是一个经典的最小点割问题。

二、最小点割模型 我们将原网格转化为一个容量网络（流网络），利用最大流最小割定理求解。

对于每个格子 $u$，将其拆为入点 $u_{in}$ 和出点 $u_{out}$，并连一条有向边 $u_{in} \to u_{out}$，容量为删除该格子的代价：

• 若格子为狼（'W'），容量为 $h$；
• 若格子为空（'.'），容量为 $b$；
• 若格子为羊（'S'），容量为 $+\infty$（不可删除）。

对于网格中相邻的两个格子 $u, v$（共享一条边），添加两条无穷大容量的边：$u_{out} \to v_{in}$ 和 $v_{out} \to u_{in}$，表示狼可以在相邻格子间自由移动（只要目标点未被删除）。

建立超级源点 $S$ 和超级汇点 $T$：

• $S$ 向每个狼格子的入点 $u_{in}$ 连一条容量为 $+\infty$ 的边，表示所有狼初始都是威胁来源；
• 羊的出点 $u_{out}$（羊所在格子拆出的出点）向 $T$ 连一条容量为 $+\infty$ 的边，表示羊是我们要保护的目标。

在这个网络中，一个 $S$-$T$ 割对应一种删除方案：被割断的 $u_{in} \to u_{out}$ 边表示该格子被删除（花费其容量）。割的容量就是总花费。由于羊的入出边容量为 $+\infty$，它永远不会被割断（不可删除）。狼的入边 $S \to u_{in}$ 为 $+\infty$，所以割不会选择这些边，而是选择删除狼点本身（$u_{in} \to u_{out}$）或删除其他中间空格。因此，最小割的容量即为保证狼与羊不连通的最小花费。

三、算法实现 我们使用 Dinic 算法求最大流。由于网络中的边权较大（可达 $10^9$），使用 64 位整数（long long）存储流量。

建图步骤：

1. 给每个格子编号 $id = r \times n + c$（行 $r \in \{0,1\}$，列 $c \in [0, n-1]$）。设总格点数 $N = 2n$。
2. 拆点：入点编号为 $2 \times id$，出点编号为 $2 \times id + 1$。超级源 $S = 4n$，超级汇 $T = 4n + 1$。总点数 $V = 4n + 2$。
3. 对于每个格子：
   • 若是 'S'：加边 $in \to out$，容量 INF；
   • 若是 'W'：加边 $in \to out$，容量 $h$；同时加边 $S \to in$，容量 INF；
   • 若是 '.'：加边 $in \to out$，容量 $b$。
4. 对于每个格子，遍历其四个方向邻居（上下左右），若邻居在界内，加边 $u_{out} \to v_{in}$，容量 INF。
5. 找到羊所在的格子，设其出点为 $sheep_{out}$，加边 $sheep_{out} \to T$，容量 INF。
6. 执行 Dinic 计算 $S$ 到 $T$ 的最大流，即为答案。

正确性：由最小割最大流定理，网络的最大流等于最小割的容量。上述网络的 $S$-$T$ 割与合法的删除方案一一对应，且割的容量等于总花费。注意到题目保证羊的相邻格子没有狼，这确保了初始状态下不会出现狼与羊直接相邻导致必须割 $S$ 或 $T$ 的边（容量无穷）的情况，从而保证最小割有限。

四、复杂度分析

• 点数量：$V = 4n + 2$，对于所有测试用例 $\sum n \le 2 \times 10^5$，总点数 $\le 8 \times 10^5 + 2 \times 1200$。
• 边数量：每个格子内部边 $1$ 条，源汇相关边 $O(狼数量)$，相邻边（双向）至多约 $2 \times 3n = 6n$ 条，总数 $O(n)$。所有测试用例总边数 $\le 2 \times 10^6$ 级别。
• Dinic 算法在网格图上的实际运行效率很高，虽然理论上界为 $O(V^2 E)$，但远无法达到。在 $\sum n = 2 \times 10^5$ 下足以在 $2$ 秒内通过。