Kotlin Heroes: Episode 11 |
---|
Finished |
In a game you started playing recently, there is a field that can be represented as a rectangular grid. The field has $$$2$$$ rows and $$$n$$$ columns — $$$2n$$$ cells in total.
Some cells are empty, but some are occupied by wolves. In the beginning of the game, you have one sheep in some cell, and you'd like to save it from wolves.
Wolves will attack you at night, so you still have some time for preparation. You have two ways to deal with wolves:
Let's say that a wolf can reach the sheep if there is a path that starts at the wolf's cell and finishes at the sheep's cell. This path shouldn't contain any cells with trenches, and each two consecutive cells in the path should be neighbors (share a side).
What is the minimum total amount of money you should pay to ensure that none of the wolves can reach the sheep?
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1200$$$) — the number of test cases. Next, $$$t$$$ independent cases follow.
The first line of each test case contains three integers $$$n$$$, $$$h$$$, and $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le h, b \le 10^9$$$) — the size of the grid and corresponding costs.
The next two lines contain a description of the grid. The $$$j$$$-th character in the $$$i$$$-th line is either '.', 'S' or 'W':
Additional constraints:
For each test case, print a single integer — the minimum total amount of money you should pay to save your sheep.
42 3 7S...2 3 7S..W2 7 3S..W4 999999999 1000000000W.S.W..W
0 3 6 2999999997
26 6 7W....WW.S..W6 6 7W...WW..S..W
21 20
One of the optimal strategies in the first test case of the second test can be shown like this:
W....W | $$$\Rightarrow$$$ | W.#..W |
W.S..W | W#S#.W |
W...WW | $$$\Rightarrow$$$ | W..#WW |
..S..W | ..S#.W |
Name |
---|