#贪心
### 补充题目
- 对于 $1\times 2$ 的瓷砖，你不可以竖着放（即 $2\times 1$ 的形式）；
- 有可能全部铺 $1\times 1$ 的瓷砖会更优。
### 思路
看到不可以竖着放，我们会很自然地使用贪心。
对于每一行，我们都单独处理。每两个相邻的字符 `.`，我们都可以使用 $1\times 2$ 或者是 $1\times 1$ 的瓷砖来填充，取 $\min$ 值即可。如果只剩下了一个 `.`，我们就使用 $1\times 1$ 的瓷砖。
### 贪心正确性判断
- 对于偶数个连续的 `.`，我们可以全部分成一节节的两个字符的组合，取 $\min$ 值；
- 对于奇数个连续的 `.`，我们可以拆分成偶数个连续的 `.` 加上一个 `.`（$1\times 1$）。
因此这个贪心完全正确。
### 代码
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int t, n, m, x, y, ans;
string s;
int main() {
for (cin >> t; t; --t) {
cin >> n >> m >> x >> y, ans = 0;
for (int i = 1; i <= n; ++i) { // 将矩阵分行处理
cin >> s, s += ' '; // 尾随空格，防止当i=m-1的时候i+1越界
for (int i = 0; i < s.size(); ++i) {
bool o = s[i] == '.' && s[i + 1] == '.'; // 判断是否能铺1*2的瓷砖
if (o) { // 如果可以
s[i] = s[i + 1] = '*' /*不管怎么样，最后都会被铺满*/,
ans += min(2 * x, y); // 只需取1*1和1*2的最小值
} else if (s[i] == '.') {
s[i] = '*', ans += x; // 不行的话就直接铺1*1的瓷砖
}
}
}
cout << ans << '\n';
}
return 0;
}
```