Two waterworks want to connect to each other with water pipes. Just as the map shows, the waterworks sit on two corners of the city. The city is a rectangle, and is divided into a lot of small squares. Water pipes are placed in these squares. Only one pipe can be placed in each square. There are two types of pipe: straight pipe and bend pipe. You can rotate them if necessary. Two types of pipe have different prices. You are assigned to calculate the minimum cost to connect the two waterworks.
Input:
There are several test cases. Each test case contains two parts.
The first part is a line of for integers: the width of the city, the length of the city, the price of the straight pipe, the price of the bend pipe(1<=width,length<=100, 0<=price<=100).
The second part is a map of the city, "b" stands for block on that square, while "*" stands for a blank square which you can place water pipe in.
Output:
For each test case, print in one line the minimum cost to connect the waterworks. If can not to connect to each other, output "impossible".
Sample Input:
1 2 3 4
*
*
5 5 8 0
b****
**bb*
**bb*
5 5 8 10
b****
**bb*
**bb*
1 1 38 89
*
1 1 3 3
b
Sample Output:
8
8
76
38
impossible
http://blog.csdn.net/libin56842/article/details/38146245
CSDN (Chinese Software Developer Network) 创立于1999年，是中国最大的IT社区和服务平台，为中国的软件开发者和IT从业者提供知识传播、职业发展、软件开发等全生命周期服务，满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。拥有超过3000万注册会员（其中活跃会员800万）、50万注册企业及合作伙伴。