题解 | 小红的矩阵染色

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    char a[1005][1005];  // 原矩阵
    vector<int> segments;  // 每段连续o的数量

    // 输入矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // 对每一列找连续的o
    for (int col = 0; col < m; col++) {
        int cnt = 0;
        for (int row = 0; row < n; row++) {
            if (a[row][col] == 'o') {
                cnt++;
            } else {
                if (cnt >= 2) segments.push_back(cnt);
                cnt = 0;
            }
        }
        if (cnt >= 2) segments.push_back(cnt);  // 列底部也要判断
    }

    // 得分段：每段长度cnt → 能得 cnt-1 分，但要涂 cnt 个格子
    sort(segments.begin(), segments.end(), greater<int>());  // 优先长段

    int score = 0, used = 0;

    for (int i = 0; i < segments.size(); i++) {
        int len = segments[i];
        if (used + len <= k) {
            used += len;
            score += (len - 1);
        } else {
            int rem = k - used;
            if (rem >= 2) score += (rem - 1);  // 只用剩下的红格也能得分
            break;
        }
    }

    cout << score << endl;
    return 0;
}

有点难