← 返回题目列表

Codeforces · 2011/D

D. 狼群之中

中文机器翻译题面 查看原题

在您最近开始玩的游戏中,有一个可以表示为矩形网格的字段。该字段有 $$$2$$$ 行和 $$$n$$$ 列 - 总共 $$$2n$$$ 个单元格。

有些牢房是空的,但有些却被狼占据了。在游戏开始时,你在某个牢房里有一只羊,你想把它从狼手中救出来。

狼会在晚上袭击你,所以你还有一些准备时间。对付狼有两种方法:

1. 你向猎人支付 $$$h$$$ 硬币并选择一个被狼占据的牢房。猎人将清理牢房,消灭里面的狼。
2. 您向建造者支付 $$$b$$$ 硬币并选择一个空单元格。建造者将在选定的牢房中挖一条狼无法穿越的沟渠。

假设有一条路径从狼的牢房开始并在羊的牢房结束,那么狼就可以到达羊。该路径不应包含任何带沟槽的单元,并且路径中的每两个连续单元应是相邻的(共享一侧)。

为了确保没有一只狼能够到达羊的身边,您至少需要支付多少钱?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1200$$$) — 测试用例的数量。接下来是 $$$t$$$ 独立案例。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$h$$$ 和 $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le h, b \le 10^9$$$) — 网格的大小和相应的成本。

接下来的两行包含网格的描述。第 $$$i$$$ 行中的第 $$$j$$$ 字符是 '.'、'S' 或 'W':

- '.'表示单元格是空的;
- 'S' 表示该单元格被羊占用;网格上只有一个这样的单元格;
- 'W' 表示该单元格被狼占据。

附加限制:

- 与羊格相邻的格子中没有狼;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您为拯救羊而应支付的最低总金额。

示例

输入 #1

4
2 3 7
S.
..
2 3 7
S.
.W
2 7 3
S.
.W
4 999999999 1000000000
W.S.
W..W

输出 #1

0
3
6
2999999997

输入 #2

2
6 6 7
W....W
W.S..W
6 6 7
W...WW
..S..W

输出 #2

21
20

注意

第二个测试的第一个测试用例中的最佳策略之一可以如下所示:

W....W$$$\右箭头$$$W.#..WW.S..WW#S#.W

W...WW$$$\右箭头$$$W..#WW..S..W..S#.W