P13038 [GCJ 2021 #2] Retiling
题目描述
Cody-Jamal 最新的艺术装置是一个可以重新铺设不同图案的厨房瓷砖地面。地面由 $\mathbf{R}$ 行 $\mathbf{C}$ 列的正方形瓷砖组成。每块瓷砖都是双面的，一面是品红色（M），另一面是绿色（G）。
要重新铺设厨房地面，允许进行以下两种操作：
* **翻转**一块瓷砖，将其可见面从品红色变为绿色，或反之，每次操作花费 $\mathbf{F}$ 枚硬币；
* **交换**两块相邻的瓷砖（水平或垂直相邻，不包括对角线相邻），不翻转任何瓷砖，每次操作花费 $\mathbf{S}$ 枚硬币。
观看 Cody-Jamal 的艺术地面是免费的，但与之互动需要花费硬币。已知地面的当前状态和目标图案，求最少需要花费多少枚硬币才能将地面从当前状态转变为目标图案。
输入格式
输入第一行包含测试用例数量 $\mathbf{T}$。每个测试用例包含：
1. 第一行四个整数 $\mathbf{R}$、$\mathbf{C}$、$\mathbf{F}$、$\mathbf{S}$，分别表示地面的行数、列数、翻转操作的花费和交换操作的花费；
2. 接下来 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，表示地面的当前状态（$\mathsf{M}$ 表示品红色，$\mathsf{G}$ 表示绿色）；
3. 最后 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，表示目标图案（字符编码与当前状态相同）。
输出格式
对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将地面转变为目标图案所需的最小硬币花费。
说明/提示
**样例解释**
在样例 #1 中：
- 当前状态与目标图案有 5 处颜色不同；
- 最少需要 3 次操作（每次操作最多改变 2 处颜色）；
- 一种最优方案：
1. 交换第一行最左两块瓷砖；
2. 交换第一行最右两块瓷砖；
3. 翻转右下角瓷砖。
在样例 #2 中：
- 有 6 处颜色需要改变；
- 由于只能通过交换同时改变两处颜色，最少需要 4 次操作；
- 一种最优方案：
1. 交换中间列最上两块瓷砖；
2. 翻转右上角瓷砖；
3. 交换最右列最下两块瓷砖；
4. 翻转最左列中间瓷砖。
测试集 2 的样例中：
- 翻转操作非常昂贵，应尽量避免；
- 由于目标图案比当前状态多 1 块品红色瓷砖，必须至少进行 1 次翻转；
- 最优方案（花费 1003 枚硬币）：
1. 交换最左两块瓷砖；
2. 翻转最右瓷砖；
3. 交换左数第二和第三块瓷砖；
4. 交换左数第三和第四块瓷砖。
**限制条件**
- $1 \leq \mathbf{T} \leq 100$；
- $1 \leq \mathbf{R} \leq 10$；
- $1 \leq \mathbf{C} \leq 10$。
**测试集 1（11 分，可见判定）**
- $\mathbf{F}=1$；
- $\mathbf{S}=1$。
**测试集 2（23 分，隐藏判定）**
- $1 \leq \mathbf{F} \leq 10^{6}$；
- $1 \leq \mathbf{S} \leq 10^{6}$。
翻译由 DeepSeek V3 完成