动态规划解决带约束的网格涂色问题

网格涂色问题是一个经典的组合优化问题。给定一个 $m \times n$ 的网格，每个格子可以涂上 $k$ 种颜色之一。约束条件为：任意两个相邻格子（共享上、下、左、右边）不能涂相同颜色。目标是计算所有合法涂色方案的数量。动态规划（DP）是解决此类问题的有效方法，通过状态转移高效地累积方案数。

问题分析

• 网格结构：网格有 $m$ 行和 $n$ 列，每个格子涂色时需满足相邻约束。
• 约束条件：
  • 同一行内，相邻格子颜色不同。
  • 相邻行之间，对应列（上下）的格子颜色不同。
• 状态定义：由于约束涉及整行，DP 状态可以基于“行配置”定义。每行的配置是一个长度为 $n$ 的序列，表示该行每个格子的颜色（颜色索引从 $0$ 到 $k-1$）。
• DP 思路：
  1. 预处理所有合法行配置：生成所有可能行配置，并过滤出满足行内相邻格子不同色的配置。
  2. 状态转移：
     • $dp[i][s]$ 表示处理到第 $i$ 行时，该行配置为 $s$ 的方案数。
     • 对于第 $i$ 行（$i \geq 1$），枚举所有合法配置 $s$，并从第 $i-1$ 行的合法配置 $t$ 转移，条件是 $s$ 和 $t$ 兼容（即对应列上下格子不同色）。
     • 转移方程：$$ dp[i][s] = \sum_{t \text{ 与 } s \text{ 兼容}} dp[i-1][t] $$
  3. 初始化和结果：
     • 第一行（$i=0$）：所有合法配置 $s$ 的 $dp[0][s] = 1$。
     • 最后一行（$i=m-1$）：总方案数为所有合法配置 $s$ 的 $dp[m-1][s]$ 之和。
• 复杂度：状态数为 $O(m \cdot k^n)$，因为每行最多有 $k^n$ 种配置。实际中，$n$ 较小时可行（例如 $n \leq 5$）。

C++ 实现步骤

1. 辅助函数：
   • isValidConfig：检查一行配置是否行内合法（相邻格子不同色）。
   • isCompatible：检查两行配置是否兼容（对应列上下格子不同色）。
   • generateRowConfigs：生成所有合法行配置。
2. 主函数：
   • 预处理所有合法行配置。
   • 初始化 DP 表（第一行方案数）。
   • 迭代更新 DP 表（行间转移）。
   • 累加最终方案数。
3. 优化：使用整数索引表示配置，避免直接存储向量，提高效率。

C++ 代码实现

以下代码实现了上述逻辑。假设 $m$ 和 $n$ 较小（例如 $n \leq 5$），否则状态空间可能过大。

#include <iostream>
#include <vector>
using namespace std;

// 检查一行配置是否行内合法（相邻元素不同）
bool isValidConfig(const vector<int>& config) {
    int n = config.size();
    for (int j = 0; j < n - 1; ++j) {
        if (config[j] == config[j + 1]) {
            return false; // 相邻格子同色，非法
        }
    }
    return true;
}

// 检查两行配置是否兼容（对应列上下元素不同）
bool isCompatible(const vector<int>& config_prev, const vector<int>& config_curr) {
    int n = config_prev.size();
    for (int j = 0; j < n; ++j) {
        if (config_prev[j] == config_curr[j]) {
            return false; // 上下格子同色，不兼容
        }
    }
    return true;
}

// 生成所有合法行配置（长度为 n，每个元素在 [0, k-1] 内）
vector<vector<int>> generateRowConfigs(int n, int k) {
    vector<vector<int>> configs;
    vector<int> current(n, 0);
    // 递归生成所有配置
    function<void(int)> generate = [&](int idx) {
        if (idx == n) {
            if (isValidConfig(current)) {
                configs.push_back(current);
            }
            return;
        }
        for (int color = 0; color < k; ++color) {
            current[idx] = color;
            generate(idx + 1);
        }
    };
    generate(0);
    return configs;
}

// 主函数：计算涂色方案数
long long countColorings(int m, int n, int k) {
    if (m == 0 || n == 0) return 0; // 空网格
    if (k <= 0) return 0; // 无颜色可用

    // 步骤1: 生成所有合法行配置
    vector<vector<int>> configs = generateRowConfigs(n, k);
    int num_configs = configs.size();
    if (num_configs == 0) return 0; // 无合法配置

    // 步骤2: 初始化 DP 表 (dp[i] 表示第 i 行各配置的方案数)
    vector<long long> dp(num_configs, 0);
    // 第一行：所有合法配置方案数为 1
    for (int s = 0; s < num_configs; ++s) {
        dp[s] = 1;
    }

    // 步骤3: 迭代处理后续行
    for (int i = 1; i < m; ++i) {
        vector<long long> new_dp(num_configs, 0); // 新行 DP 表
        for (int s_curr = 0; s_curr < num_configs; ++s_curr) { // 当前行配置索引
            for (int s_prev = 0; s_prev < num_configs; ++s_prev) { // 上一行配置索引
                // 如果两行兼容，转移方案数
                if (isCompatible(configs[s_prev], configs[s_curr])) {
                    new_dp[s_curr] += dp[s_prev];
                }
            }
        }
        dp = move(new_dp); // 更新 DP 表
    }

    // 步骤4: 累加最后一行所有配置的方案数
    long long total = 0;
    for (long long count : dp) {
        total += count;
    }
    return total;
}

// 示例使用
int main() {
    int m = 2; // 行数
    int n = 2; // 列数
    int k = 2; // 颜色数
    long long result = countColorings(m, n, k);
    cout << "涂色方案数: " << result << endl; // 输出应为 2（例如：颜色0和1交替）
    return 0;
}

代码说明

• 输入参数：m（行数）、n（列数）、k（颜色数）。
• 输出：合法涂色方案的总数（类型为 long long 避免溢出）。
• 关键部分：
  • generateRowConfigs：递归生成所有行配置，并过滤非法配置（行内相邻不同色）。
  • DP 转移：使用二维迭代，时间复杂度 $O(m \cdot c^2)$，其中 $c$ 是合法配置数（$c \leq k^n$）。
  • 兼容性检查：确保行间上下格子不同色。
• 边界处理：网格为空或无颜色时返回 0。
• 示例测试：m=2, n=2, k=2 时，方案数为 2（例如：第一行 [0,1]，第二行 [1,0]；或第一行 [1,0]，第二行 [0,1]）。

复杂度与优化

• 时间复杂度：$O(m \cdot c^2)$，其中 $c$ 是合法行配置数（$c \leq k^n$）。当 $n$ 小（如 $n \leq 5$）时高效。
• 空间复杂度：$O(c)$，DP 表只存储当前行状态。
• 优化建议：
  • 如果 $n$ 大，可改用状态压缩（位运算）减少状态数。
  • 使用记忆化或滚动数组优化内存。
  • 对于固定 $k$，可预计算兼容性矩阵。

此实现保证了正确性和可读性。实际使用时，请根据网格大小调整参数。