题解 | 小红的矩阵修改

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for (int i = 0; i < n; ++i) {
        cin >> mat[i];
    }

    // 将输入转换为数值矩阵，并转置为按列存储
    vector<vector<int>> cols(m, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c = mat[i][j];
            if (c == 'r') cols[j][i] = 0;
            else if (c == 'e') cols[j][i] = 1;
            else cols[j][i] = 2;
        }
    }

    // 生成所有可能的状态
    vector<vector<int>> all_states;
    function<void(int, vector<int>&)> dfs = [&](int row, vector<int>& current) {
        if (row == n) {
            all_states.push_back(current);
            return;
        }
        for (int c = 0; c < 3; ++c) {
            if (!current.empty() && current.back() == c) continue;
            current.push_back(c);
            dfs(row + 1, current);
            current.pop_back();
        }
    };
    vector<int> tmp;
    dfs(0, tmp);
    int num_states = all_states.size();

    // 预处理状态转移矩阵
    vector<vector<bool>> transition(num_states, vector<bool>(num_states, false));
    for (int p = 0; p < num_states; ++p) {
        for (int q = 0; q < num_states; ++q) {
            bool valid = true;
            for (int i = 0; i < n; ++i) {
                if (all_states[p][i] == all_states[q][i]) {
                    valid = false;
                    break;
                }
            }
            transition[p][q] = valid;
        }
    }

    // 预处理每个状态在各列的修改成本
    vector<vector<int>> cost(m, vector<int>(num_states));
    for (int j = 0; j < m; ++j) {
        for (int s = 0; s < num_states; ++s) {
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (all_states[s][i] != cols[j][i]) {
                    cnt++;
                }
            }
            cost[j][s] = cnt;
        }
    }

    // 动态规划
    vector<int> prev_dp(num_states, INT_MAX);
    for (int s = 0; s < num_states; ++s) {
        prev_dp[s] = cost[0][s];
    }

    for (int j = 1; j < m; ++j) {
        vector<int> current_dp(num_states, INT_MAX);
        for (int prev_s = 0; prev_s < num_states; ++prev_s) {
            if (prev_dp[prev_s] == INT_MAX) continue;
            for (int curr_s = 0; curr_s < num_states; ++curr_s) {
                if (transition[prev_s][curr_s]) {
                    if (prev_dp[prev_s] + cost[j][curr_s] < current_dp[curr_s]) {
                        current_dp[curr_s] = prev_dp[prev_s] + cost[j][curr_s];
                    }
                }
            }
        }
        prev_dp = move(current_dp);
    }

    int ans = *min_element(prev_dp.begin(), prev_dp.end());
    cout << ans << endl;

    return 0;
}

deepseek思考600秒后给出正解

方法思路

1. 状态生成：生成所有可能的行状态，每个状态是一个满足相邻字符不同的字符序列。
2. 转移矩阵：预处理所有可能的状态转移，确保相邻列的状态在每一行上的字符都不同。
3. 动态规划：使用动态规划来计算从第一列到最后一列的最小修改次数，维护每个状态的最小修改次数，并利用预处理的状态转移来更新当前状态的最小值。