|
F |
Electricity
Connection Input: Standard Inputr Output: Standard Output |
|
The city 'AjobakahD' has a lot
of problems with electricity. Load shedding is a common problem here and people
are quite used to it. Instead of calculating the total time the power is on,
they calculate the total time the power is off. And of course the later one is
always greater.
There is a small area in the
city, which has not yet been enlightened with any load shedding! That means
they haven’t got the electricity connection yet. Now the Power Development
Board (PDB) wants to set electricity connection in that area. Since the overall
power in that city is not sufficient, they have decided to build a power generator
in that area and want to connect all the houses to the generator.
The area can be modeled as an 8 x 8 grid. Each cell contains one of
the following characters
'.'
means land
'H'
means house
'G'
means power generator
'W'
means water
Two adjacent
cells can be connected by cables and the cost is 1 thousand. Two cells are said to be adjacent if they share a side.
But two adjacent cells can only be connected if none of the cells is empty.
Empty means either land or water. In such case, pillars can be built in the
cells and after that they can be connected. The cost of placing a pillar in a
land and water cell is pl and pw thousand respectively. Remember that
both the costs can be zero, because there can be sponsors who might use the
pillars to advertise themselves.
Now given the modeled grid of the area, the PDB wants to find the minimum cost to connect all the houses to the power generator directly or indirectly. That’s why they seek your help, as you are one of the finest programmers in town.
Input
Input starts with a positive
integer T
(T≤ 200) denoting the number of cases.
Each
case starts with two integers pl and
pw (0 ≤ pl, pw ≤ 10). Then there will be 8 lines, each containing 8 characters from the set {., H, G, W}. You may
assume that in any modeled grid, there is exactly one power generator and the
total number of houses is between 1
and 8 (inclusive).
Output
For each test case, print the case number and the total cost in thousands. Look at the output for sample input for formatting details.
Sample
Input
Output for Sample Input
|
2 0 10 H.W.WH.. ..W.W... ..WGW... ........ ........ ........ ........ ........ 0 0 H.W.WH.. ..W.W... ..WGW... ........ ........ ........ ........ ........ |
Case 1: 12 Case 2: 7 |
Problemsetter: Jane Alam
Jan, Special Thanks: Derek Kisman