水塘 Pool construction
题意翻译
## 题意翻译
给定一个 $n \times m$ 的矩阵（陆地），每个格子要么是草（用#代替），要么是水洼（用.代替）。你要将它变成游泳池。
有下述修改方法或要求：
- 将**草地**变成**水洼**，要花费 $d$ 元。
- 将**水洼**变成**草地**，要花费 $f$ 元。
- 对矩阵边缘有要求，必须全部为草地。
- 要在水洼和草地之间修筑围墙。每个单位的围墙要花费 $b$ 元。
请你计算出最小花费。
## 输入格式：
第一行是一个整数 $T$ ，表示测试组数。
对于每组数据，第一行，给出矩阵的范围 $n$ 和 $m$ （ $ 2 \leq n,m \leq 50$）。
接下来依次给出三个整数 $d,f,b$ （ $1 \leq d,f,b \leq 10000$ ） 。
最后给出$n \times m$ 矩阵的具体信息。
## 输出格式：
每行一个整数，第 $i$ 行表示第 $i$ 组数据的最小花费。
## 样例输入：
```
3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#
```
## 样例输出
```
9
27
22
```
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4261
[PDF](https://uva.onlinejudge.org/external/15/p1515.pdf)